如何在 Java 中实现链表？

How to implement a Linked List in Java?

提问by nbarraille

I am trying to implement a simple HashTable in Java that uses a Linked List for collision resolution, which is pretty easy to do in C, but I don't know how to do it in Java, as you can't use pointers...

我正在尝试在 Java 中实现一个简单的 HashTable，它使用链表来解决冲突，这在 C 中很容易实现，但我不知道如何在 Java 中实现，因为您不能使用指针.. .

First, I know that those structures are already implemented in Java, I'm not planning on using it, just training here...

首先，我知道这些结构已经在 J​​ava 中实现了，我不打算使用它，只是在这里培训......

So I created an element, which is a string and a pointer to the next Element:

所以我创建了一个元素，它是一个字符串和一个指向下一个元素的指针：

public class Element{
        private String s;
        private Element next;

        public Element(String s){
            this.s = s;
            this.next = null;
        }

        public void setNext(Element e){
            this.next = e;
        }

        public String getString(){
            return this.s;
        }

        public Element getNext(){
            return this.next;
        }

        @Override
        public String toString() {
            return "[" + s + "] => ";
        }
    }

Of course, my HashTable has an array of Element to stock the data:

当然，我的 HashTable 有一个 Element 数组来存储数据：

public class CustomHashTable {
    private Element[] data;

Here is my problem:

这是我的问题：

For example I want to implement a method that adds an element AT THE END of the linked List (I know it would have been simpler and more efficient to insert the element at the beginning of the list, but again, this is only for training purposes). How do I do that without pointer?

例如，我想实现一个方法，在链接列表的末尾添加一个元素（我知道在列表的开头插入元素会更简单、更有效，但同样，这仅用于培训目的）。没有指针我该怎么做？

Here is my code (which could work if e was a pointer...):

这是我的代码（如果 e 是一个指针，它可以工作......）：

public void add(String s){
        int index = hash(s) % data.length;
        System.out.println("Adding at index: " + index);
        Element e = this.data[index];
        while(e != null){
            e = e.getNext();
        }
        e = new Element(s);
    }

Thanks!

谢谢！

回答by Joel

public void add(String s){
    int index = hash(s) % data.length;
    System.out.println("Adding at index: " + index);
    Element curr = new Element(s);
    Element e = this.data[index];
    if (e == null) {
       this.data[index] = curr;
       return;
    }
    while(e.getNext() != null){
        e = e.getNext();
    }
    e.setNext(curr);
}

回答by duffymo

If you want to write your own, start by having it implement the java.util.List interface.

如果你想自己写，首先让它实现 java.util.List 接口。

If you can use a library class, use the java.util.LinkedList.

如果您可以使用库类，请使用 java.util.LinkedList。

Now it's been pointed out to me that you're "practicing", so some good advice might be off limits according to some, but you should be aware of generics. I'd recommend reading up on them and building them into your Element (Node?) and List implementations. Generics were born for use with collections in just this way. I'd start here:

现在有人向我指出您正在“练习”，因此根据某些人的说法，一些好的建议可能是不受限制的，但您应该了解泛型。我建议阅读它们并将它们构建到您的元素（节点？）和列表实现中。泛型就是为了以这种方式与集合一起使用而诞生的。我会从这里开始：

package list;

public class Node<T>
{
    private T value;
    private Node<T> prev;
    private Node<T> next;
    // You add the rest.
}

回答by Joey

For your purposes here Java's references are not used differently from C's pointers. In fact, the major problem (or benefit, depending on who you ask) pointers have in C is not that they can pointto something, but that you can do math with them.

出于您的目的，Java 的引用与 C 的指针的使用没有区别。事实上，C 中指针的主要问题（或好处，取决于你问的是谁）不是它们可以指向某物，而是你可以用它们做数学运算。

For just the pointing purposes, you can do the same here:

仅出于指示目的，您可以在此处执行相同操作：

e.setNext(new Element(s));

instead of

代替

e = new Element(s);

(which would just let the variable epoint to a new element, but won't change anything on the old ones).

（这只会让变量e指向一个新元素，但不会改变旧元素的任何内容）。

and you're done.

你就完成了。

回答by Jon Skeet

Reassigning a local variable at the end of a method isn't going to change anything. You need something like:

在方法结束时重新分配局部变量不会改变任何东西。你需要这样的东西：

Element e = this.data[index];
while (e.getNext() != null) {
    e = e.getNext();
}

Then erefers to the element at the end of the list. Create a new element, and set that as the next one:

然后e引用列表末尾的元素。创建一个新元素，并将其设置为下一个：

Element newElement = new Element(s);
e.setNext(newElement);

For efficiency, I'd urge you to consider doubly-linked nodes and a list type which knows about the head and tailof the list. Differentiate between the list as a whole (which knows the head, the tail, and probably the count), and a node within the list (which knows about the next, previous, and possibly what list it belongs to).

为了效率，我建议您考虑双向链接节点和知道列表头部和尾部的列表类型。区分整个列表（知道头、尾，可能还有计数）和列表中的节点（知道下一个、上一个，可能还有它属于哪个列表）。

回答by Ishtar

A recursive solution:

递归解决方案：

public class Element{
  /* ... */
  public void addTail(Element e){
    if (next == null)
      next = e; //we are at the end, add it
    else
      next.addTail(e);//let the next node take responsibility
  }
}

public void add(String s){

  int index = hash(s) % data.length;
  System.out.println("Adding at index: " + index);
  Element e = this.data[index];
  e.addTail(new Element(s));
}

回答by kamaci

LinkedList in java works as like that:

Java 中的 LinkedList 是这样工作的：

There is a static class like this:

有一个像这样的静态类：

private static class Entry<E> {
E element;
Entry<E> next;
Entry<E> previous;
Entry(E element, Entry<E> next, Entry<E> previous) {
    this.element = element;
    this.next = next;
    this.previous = previous;
}
}

LinkedList constructors:

链表构造函数：

public LinkedList() {
    header.next = header.previous = header;
}

public LinkedList(Collection<? extends E> c) {
this();
addAll(c);
}

addAll method:

addAll 方法：

public boolean addAll(Collection<? extends E> c) {
    return addAll(size, c);
}

You should check here:

你应该在这里检查：

private transient Entry<E> header = new Entry<E>(null, null, null);
private transient int size = 0;

private Entry<E> addBefore(E e, Entry<E> entry) {
Entry<E> newEntry = new Entry<E>(e, entry, entry.previous);
newEntry.previous.next = newEntry;
newEntry.next.previous = newEntry;
size++;
modCount++;
return newEntry;
}

private E remove(Entry<E> e) {
if (e == header)
    throw new NoSuchElementException();

    E result = e.element;
e.previous.next = e.next;
e.next.previous = e.previous;
    e.next = e.previous = null;
    e.element = null;
size--;
modCount++;
    return result;
}

private Entry<E> addBefore(E e, Entry<E> entry) {
Entry<E> newEntry = new Entry<E>(e, entry, entry.previous);
newEntry.previous.next = newEntry;
newEntry.next.previous = newEntry;
size++;
modCount++;
return newEntry;
}

public boolean add(E e) {
addBefore(e, header);
    return true;
}

回答by CRS

//Single linked list implementation

public class Nodes {

    int data;
    Nodes next = null;

    public Nodes(int data) {
        this.data = data;
    }
}


public class Lists {

    static Nodes first = null;

    public static void insertBegin(int data) {
        Nodes temp = new Nodes(data);
        if(first == null) {
            first = temp;
        }
        else {
            temp.next = first;
            first = temp;           
        }
    }

    public static void insertEnd(int data) {
        Nodes temp = new Nodes(data);
        if(first == null) {
            first = temp;
        }
        else{
            Nodes n = first;
            while(n.next != null) {
                n = n.next;
            }
            n.next = temp;
        }
    }

    public static void insertPos(int pos, int data) {
        Nodes temp = new Nodes(data);
        if(first == null) {
            System.out.println("List empty. Cannot insert");
        }
        else {
            Nodes n = first;
            while(n.data != pos && n.next != null) {
                n = n.next;
            }
            if(n.data != pos){
                System.out.println("Position not found");
            }
            else {
                temp.next = n.next;
                n.next = temp;
            }
        }
    }

    public static void deleteBegin() {
        if(first == null) {
            System.out.println("List empty. Cannot delete");
        }
        else {
            first = first.next;
        }       
    }


    public static void deleteEnd() {
        if(first == null) {
            System.out.println("List empty. Cannot delete");
        }
        else {
            Nodes n = first;
            while(n.next.next != null) {
                n = n.next;
            }
            n.next = n.next.next;
        }
    }

    public static void deletePos(int pos) {
        if(first == null) {
            System.out.println("List empty. Cannot delete");
        }
        else {
            Nodes n = first;
            while(n.next.data != pos && n.next.next != null) {
                n = n.next;
            }
            if(n.next.data != pos) {
                System.out.println("Element not found. Deletion failed");
            }
            else{
                n.next = n.next.next;
            }
        }
    }

    public static void printAll() {
        System.out.println("Elements in link list");
        Nodes n = first;
        while(n != null) {
            System.out.print(n.data + "->");
            n = n.next;
        }
    }
}