如何在Java中实现链接列表？
我试图在Java中实现一个简单的HashTable，它使用链接列表进行冲突解决，这在C中很容易做到，但我不知道如何用Java做，因为你不能使用指针.. 。
首先，我知道这些结构已经用Java实现了，我不打算使用它，只是在这里训练……
所以我创建了一个元素，它是一个字符串和指向下一个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 + "] => "; } } 当然，我的HashTable有一个Element数组来存储数据：
public class CustomHashTable { private Element[] data;
这是我的问题：
例如，我想实现一个方法，在链接列表的末尾添加一个元素（我知道在列表的开头插入元素会更简单，更有效，但同样，这仅用于培训目的）。 没有指针我该怎么做？
这是我的代码（如果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); }
谢谢！
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); }
出于您的目的，Java的引用与C的指针的使用方式不同。 事实上，C中的主要问题（或好处，取决于你问谁）指针并不是他们可以指出什么，而是你可以用它们做数学。
仅出于指点目的，您可以在此处执行相同的操作：
e.setNext(new Element(s));
代替
e = new Element(s);
（这只会让变量e指向一个新元素，但不会改变旧元素的任何内容）。
你已经完成了
如果你想自己编写，首先要实现java.util.List接口。
如果可以使用库类，请使用java.util.LinkedList。
现在已经向我指出你正在“练习”，所以根据一些人的说法，一些好的建议可能会不受限制，但是你应该注意generics。 我建议你阅读它们并将它们构建到你的Element（Node？）和List实现中。 仿制药就是以这种方式诞生的。 我从这里开始：
package list; public class Node { private T value; private Node prev; private Node next; // You add the rest. }
在方法结束时重新分配局部变量不会改变任何东西。 你需要这样的东西：
Element e = this.data[index]; while (e.getNext() != null) { e = e.getNext(); }
然后e指的是列表末尾的元素。 创建一个新元素，并将其设置为下一个元素：
Element newElement = new Element(s); e.setNext(newElement);
为了提高效率，我建议您考虑双链节点和一个知道列表头部和尾部的列表类型。 区分整个列表（它知道头部，尾部，可能还有计数），以及列表中的节点（它知道它所属的下一个，前一个，可能是哪个列表）。
递归解决方案：
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)); }
java中的LinkedList就像这样：
有一个像这样的静态类：
private static class Entry { E element; Entry next; Entry previous; Entry(E element, Entry next, Entry previous) { this.element = element; this.next = next; this.previous = previous; } }
LinkedList构造函数：
public LinkedList() { header.next = header.previous = header; } public LinkedList(Collection c) { this(); addAll(c); }
addAll方法：
public boolean addAll(Collection c) { return addAll(size, c); }
你应该在这里查看：
private transient Entry header = new Entry (null, null, null); private transient int size = 0; private Entry addBefore(E e, Entry entry) { Entry newEntry = new Entry (e, entry, entry.previous); newEntry.previous.next = newEntry; newEntry.next.previous = newEntry; size++; modCount++; return newEntry; } private E remove(Entry 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 addBefore(E e, Entry entry) { Entry newEntry = new Entry (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; }
//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; } } }