Java链表实现

Question

我现在正在学习链表，我有点困惑。我正在做一项作业，我们正在创建我们自己的一些方法的实现，以便与链表一起使用。

我看了很多关于链表概念以及节点如何工作（如获取数据和设置下一个元素）的视频，但我对如何制作列表来测试我正在实施的方法感到困惑。我知道这听起来可能很愚蠢，但我开始对方法中的多个参数感到非常困惑，并且涉及到 return 语句，而且我之前从未使用过通用数据类型，所以这些基本想法在这里可能会让我感到困惑。

我希望在创建列表方面得到一些帮助，这样我就可以在创建它们时测试这些方法，但我在打印列表时遇到了困难。我知道我主要做的是创建新节点并添加到某个列表，但老实说我不知道这个假定的 LinkedList 在哪里或它叫什么。任何帮助是极大的赞赏！！仅供参考，我是 Java 的新手，这是我的第二个 class，它是在线的，但结构不是很好 class，请多多关照，哈哈

我明白了这个概念，但是要将这些添加到的列表（或链表）的名称是什么？

    ListNode node4 = new ListNode("Fourth", null);
    ListNode node3 = new ListNode("Third", node4);
    ListNode node2 = new ListNode("Second", node3);
    ListNode node1 = new ListNode("First", node2);

我不知道如何像上面那样单独打印这些，因为我可以使用上面的名字

ListNode value = new ListNode("First", new ListNode("Second", new ListNode("Third", null) ));

这是我的测试代码 class，其中我有一些问题作为评论，如果我在上面没有理解，这可能会帮助您理解我感到困惑的地方。我遗漏了 ListNode class，因为它是你的基本 getNext() setNext() 节点 class，称为 ListNode，具有通用类型....

//Testing program for SinglyLinkedList class
public class LinkedListDriver {

public static void main(String[] args) {
    //List<String> list = new LinkedList<String>();                   //comment out this line to test your code
    SinglyLinkedList<String> list = new SinglyLinkedList<String>();  //remove comment to test your code
    SinglyLinkedList SLL = new SinglyLinkedList();

    ListNode node4 = new ListNode("Fourth", null);
    ListNode node3 = new ListNode("Third", node4);
    ListNode node2 = new ListNode("Second", node3);
    ListNode node1 = new ListNode("First", node2);

//ListNode value = new ListNode("First", new ListNode("Second", new ListNode("Third", null) ));

System.out.println(node2.getData());

//Is this the correct way to add a new node to this method?
    SLL.addLast(new ListNode("Fifth", null));
//I doubt my printList is correct as I do not know what parameter I am       supposed to pass to it.    
    SLL.printList();
}

单链表class

//This class implements a very simple singly-linked list of Objects
public class SinglyLinkedList<E> {
     ListNode<E> first; // first element

public SinglyLinkedList()  {
    first = null;
}

public E getFirst() {
   if (first == null) {
      throw new NoSuchElementException();
   }
   else
      return first.getData();
   }

public void addFirst(E value) {
    first = new ListNode<E>(value, first);
}

// Methods below implemented by you. Note: while writing methods, keep in mind
// that you might be able to call other methods in this class to help you - you
// don't always need to start from scratch(but you'll have to recognize when)
public void addLast(E value) {    
    ListNode<E> temp = first;
    //If list is empty make new node the first node.
    if(temp == null) {
        first = new ListNode <E>(value, null);
        first.setNext(null);
    }
    //Otherwise loop to end of list and add new node.
    else {
        while(temp.getNext() != null) {
            temp = temp.getNext();
        }
    temp.setNext(new ListNode<E>(value, null));
    }
}//end addLast

// throws an exception - you decide when and which one
public E getLast() {
    ListNode<E> temp = first;
    if(temp == null) {
        throw new NullPointerException("There are no elements in this list to get.");
    }
    else {
        while(temp.getNext() != null) {
            temp = temp.getNext();
        }
        return temp.getData();
    }
}

// throws an exception - you decide when and which one
public E removeFirst() {
    if(first == null) {
        throw new NullPointerException("There are no elements in this list to remove.");
    }
    ListNode<E> tempRemove = first;  
    return null;//just so it'll compile
  }

  // throws an exception - you decide when and which one
  public E removeLast() {
     return null; //just so it'll compile
  }

  // return the number of elements in the list
  public int size() {
      return 0;//just so it'll compile
  }

  // return true if o is in this list, otherwise false
  public boolean contains(E obj) {
      return true;//just so it'll compile
  }

 public void printList(java.io.PrintStream out) {
     if(first == null) {
        System.out.println("The list is empty");
     }
     ListNode<E> current = first;
     while(current != null) {
         System.out.println(current.toString());
         current = current.getNext();
     }
  }

  public String toString() {
       String s = "[";
       ListNode<E> current = first;
    //write code to traverse the list, adding each object on its own line
    while(current.getNext() != null) {
        current = current.getNext();
    }

  s += "]";
  return s;
  }

  // OPTIONAL: just for fun...and a challenge
  public void reverse() {
  }
}

Answer 1

链表是基本的数据结构。

一个基本的链表实现如下：

class LinkedListNode {
  int value;
  LinkedListNode next;
}

基本思想是您可以通过检查列表是否具有 next 参数来遍历列表，如下所示：while (currentNode.next != null) { ... }。

打印链表的值利用了前面提到的while循环，你只需要打印当前节点的值。

你可以把链表想象成一排人，他们只能看到前面的人，而看不到后面的人。您知道排在最前面的那个人——也就是没有人 'behind' 他的那个人——在哪里。此人称为列表的"head"。他知道谁在他的正前方，每个人都知道谁在他的正前方。当你到达某人面前没有任何人的地步时，你已经完成了整条线。

下面是将新元素添加到列表末尾的示例：

LinkedListNode node = myListHead;
while (node.next != null) {
  node = node.next;
}
node.next = new LinkedListNode(...);

Java链表实现

Java linked list implementation

java

implementation

linked-list

singly-linked-list