LinkedList：
public class StratchLinkedList {
private Node head;
private int size;
public StratchLinkedList() {
head = null;
size = 0;
}
public void add(Object data) {
Node temp = new Node(data);
Node curr = head;
if (head == null) {
head = temp;
} else {
while (curr.getNext() != null) {
curr = curr.getNext();
}
curr.setNext(temp);
}
}
public void add(Object data, int index) {
Node temp = new Node(data);
Node curr = head;
if (index == 0){
temp.setNext(head);
this.head = temp;
} else{
for(int i = 1; i < index; i++){
curr = curr.getNext();
}
temp.setNext(curr.getNext());
curr.setNext(temp);
}
this.size++;
}
public void replace(Object data, int index) {
Node curr = head;
for (int i = 0; i < 0; i++){
curr = curr.getNext();
}
curr.setData(data);
}
public Object get(int index) {
Node curr = head;
for (int i = 0; i < index; i++){
curr = curr.getNext();
}
return curr.getData();
}
public void remove(int index) {
Node curr = head;
if (index == 0) {
head = head.getNext();
} else {
for (int i = 1; i < index; i++){
curr = curr.getNext();
}
curr.setNext(curr.getNext().getNext());
}
this.size--;
}
public int size() {
return this.size;
}
public String toString() {
String list = "";
list += "[" + this.head.getData() + "]";
Node curr = head.getNext();
while (curr != null){
list += "[" + curr.getData() + "]";
curr = curr.getNext();
}
return list;
}
}
节点：
public class Node {
Node next;
Object data;
public Node(Object data) {
this(data, null);
}
public Node(Object data, Node next) {
this.next = next;
this.data = data;
}
public Object getData() {
return this.data;
}
public void setData(Object data) {
this.data = data;
}
public Node getNext() {
return this.next;
}
public void setNext(Node nextNode) {
this.next = nextNode;
}
}
编辑：代码正在开发中。
public class StratchLinkedList<T> {
private Node head;
private Node tail;
private int size;
public StratchLinkedList() {
head = null;
tail = null;
size = 0;
}
public void insert(T data, int index) {
if (index > size) {
throw new IllegalArgumentException("The index [" + index
+ "] is greater than the currentent size [" + size + "].");
} else {
Node temp = new Node(data);
Node current = getNode(index);
if (index == 0) {
temp.setNext(head);
head = temp;
tail = head;
} else {
temp.setNext(current.getNext());
current.setNext(temp);
}
if ( index == size - 1 ) {
tail.setNext(temp);
tail = temp;
}
}
size++;
}
public void append(T data) {
insert(data, size);
}
public void replace(T data, int index) {
getNode(index).setData(data);
}
public void remove(int index) {
if (index == 0) {
head = head.getNext();
} else {
getNode(index).setNext(getNode(index).getNext().getNext());
}
this.size--;
}
private Node getNode(int index) {
if ( index > size ) {
throw new IllegalArgumentException("The index [" + index + "] is greater than the current size [" + size + "].");
}
Node current = head;
for (int i = 1; i < index; i++) {
current = current.getNext();
}
return current;
}
public T get(int index) {
return getNode(index).getData();
}
public int size() {
return this.size;
}
public String toString() {
StringBuilder builder = new StringBuilder();
Node current = head;
while( current != null ) {
builder.append("[" + current.getData() + "]");
current = current.getNext();
}
return builder.toString();
}
private class Node {
Node next;
T data;
public Node(T data) {
this(data, null);
}
public Node(T data, Node next) {
this.next = next;
this.data = data;
}
public T getData() {
return this.data;
}
public void setData(T data) {
this.data = data;
}
public Node getNext() {
return this.next;
}
public void setNext(Node nextNode) {
this.next = nextNode;
}
}
}
#1 楼
不要重复（DRY）public void add(Object data) {
Node temp = new Node(data);
Node curr = head;
if (head == null) {
head = temp;
} else {
while (curr.getNext() != null) {
curr = curr.getNext();
}
curr.setNext(temp);
}
}
您有一个
size字段，因此您应该在此功能中对其进行更新。 实际上，您可以更简单地编写此函数：
public void add(Object data) {
add(data, size);
}
这样可以减少重复的代码，简化维护。它还消除了您不更新大小的错误。这是重复代码不好的主要原因之一：容易产生不一致的结果。
不信任您的输入
public void add(Object data, int index) {
Node temp = new Node(data);
Node curr = head;
if (index == 0){
temp.setNext(head);
this.head = temp;
} else{
for(int i = 1; i < index; i++){
curr = curr.getNext();
}
temp.setNext(curr.getNext());
curr.setNext(temp);
}
this.size++;
}
如果
index > size会发生什么？尝试在列表末尾取消引用NullPointerException指针时，将抛出null。这是毫无根据的。有几种选择。发生这种情况时，您可以用空白节点填充列表，但是如果这是无意的，那将毫无用处。您可能会抛出一个更有用的异常： if ( index > size ) {
throw new IllegalArgumentException("The index [" + index + "] is greater than the current size [" + size + "].");
}
，或者您可以默默地充当
index等于size并继续：br />
如果添加到列表的末尾是常见的，则还有另一种选择：
if ( index > size ) {
index = size;
}
这将添加一个新的
tail变量，该变量指向列表的末尾。请注意，如果您这样做，则必须进行其他更改以维护tail变量。如果您不维护tail，请考虑将默认值添加到列表的最前面。这在链接列表中很简单，但是当列表被单链接时，添加到末尾很难。 除非您有命名冲突（例如，函数参数），否则不必将
this.与字段名称一起使用。因此，您只能说 if ( null == tail ) {
tail = head;
}
} else if ( index >= size ) {
tail.setNext(temp);
tail = temp;
DRY Part II
函数
replace，get和remove也应注意index不在列表中的情况。对于replace和get，您可能想要定义要使用的find函数，例如 size++;
，并定义为类似
Node current = find(index);
请注意，我正在写
current而不是将其缩写为curr。读取时节省的秒数将超过键入它所花费的秒数。不一定是今天，而是六个月后，您需要花点时间记住curr的含义。当然，任何其他阅读它的人都会立即发现它。有用的代码要比编写的要多，因此针对常见情况进行优化是有意义的。 StringBuilder
private Node find(int index) {
if ( index >= size ) {
throw new IllegalArgumentException("The index [" + index + "] is greater than the current size [" + size + "].");
}
Node current = head;
for ( int i = 0; i < index; i++ ) {
current = current.getNext();
}
}
考虑使用
String而不是StringBuilder。 StringBuilder设计用于附加。常规String值不是。每次在+=上使用String都会隐式创建一个新的String。如果幸运的话，编译器可能会重写您的版本以改用StringBuilder。 public String toString() {
String list = "";
list += "[" + this.head.getData() + "]";
Node curr = head.getNext();
while (curr != null){
list += "[" + curr.getData() + "]";
curr = curr.getNext();
}
return list;
}
请注意，此代码还处理空列表的情况，而原始代码则不行（如果用空列表调用，则会抛出
NullPointerException，例如它将尝试取消引用null head）。 #2 楼
欢迎使用CodeReview！我不是Java专家，但希望我可以看一下。总体看来还不错，但是我有一些注意事项。
出于学习目的，Object很好，但是在实际的实现中，您将需要使用泛型。真的，因为围绕此的泛型非常简单，所以使用泛型进行编码可能是一个很好的介绍。
for (int i = 0; i < 0; i++){
curr = curr.getNext();
}
我认为那是一个错字？如果您以前没有做过的话，这也可能是单元测试的不错的介绍。
您似乎以许多不同的方式执行了“使节点位于索引x”的操作的地方。应该将其拉出到方法中。
Node是List的实现细节。它不应该是消费者可以看到的
public类。不必在每次添加元素时都遍历列表，而应存储尾部引用，这样它可以是恒定时间线性。
我会考虑从列表中省略慢速操作。当人们使用某种数据结构时，他们倾向于假定其上的所有方法都是相对有效的。
要使用高级语言编写链接列表，您确实需要一个迭代器。这样一来，您就可以在不公开
add(Iterator location, Object data)的情况下完成诸如恒定时间Node之类的所有不错的事情（不使用迭代器的方法是仅使用getHead()方法，然后直接在节点上进行：/）。这也使列表的遍历变得更整洁，并且，此外，如果列表要实现Iterable，则可以在for-each循环中使用它。类内容是通常在类声明下缩进：
public class SomeClass {
public SomeClass() {}
}
当然归结为个人风格，但我从未见过类实现与声明齐平。
这是更小的事情，但是除非有必要，否则人们在访问属性时往往会忽略
this。public void replace(Object data, int index)
我希望替换方法能够返回存储在列表中的旧值。
您应验证索引值是否在列表的范围内。
IllegalArgumentException比NullPointerException更有意义。 （尽管，当然可以让NPE发生……）。注意：迭代器使提供无效索引变得更加困难。
您应该在
StringBuilder中使用toString。通常情况并不重要，但是对于一个可能很大的容器而言，这可能是有意义的性能差异。您可以考虑使用哨兵节点。它使您可以简化头节点周围的一些特殊情况（就像我在Brython发现错误之前尝试做的那样），并使列表的推理更加容易。不幸的是，它也浪费了一点空间，分配了空间，并使一个空列表实际上在构造上做了不平凡的事情，但是……除了最受限制的情况之外，所有缺点都没有关系。
评论
\ $ \ begingroup \ $
+1，以避免操作缓慢。使make add（Object）在头插入模式，或维护指向最后一个节点的指针，以便快速附加到末尾。
\ $ \ endgroup \ $
– 200_success
2015年2月27日下午6:39
#3 楼
这是一个错误：：您的循环逻辑不正确！
public void replace(Object data, int index) {
Node curr = head;
for (int i = 0; i < 0; i++){
curr = curr.getNext();
}
curr.setData(data);
}
为了娱乐：
实现一个可以合并2个类似节点的方法
将节点插入列表顶部的方法
查找最小/最大值
搜索特定值
#4 楼
为了使您的类在实际项目中更有用，您可以将其转变为通用类。这样，您的类的用户可以创建StratchLinkedList<String>，StratchLinkedList<Integer>或StratchLinkedList<SomeClassOfMyOwn>，其中所有方法都采用并返回给定类型，而不是Object。这样可以防止不必要的类型转换，并在与您的类进行交互时提高类型安全性。您可以考虑的另一个改进是实现一些接口，例如
Iterable甚至Collection。这将允许标准库中的许多算法与您的类无缝交互。#5 楼
我知道该线程已经使用了一年多，但是对于后代来说...Brythan的答案非常好，但是StringBuilder部分仍然有改进的余地。
builder.append("[" + current.getData() + "]");
在循环中发现的
很可能会被Java编译器转换为：
builder.append(new StringBuilder().append("[").append(current.getData()).append("]").toString());
但是，我们可以直接附加到
builder并避免每次迭代都创建新的StringBuilder对象和toString（）调用：builder.append("[").append(current.getData()).append("]");
评论
\ $ \ begingroup \ $
我支持您的回答，因为我认为执行多次追加操作更简洁，但是您是否有一个清晰的示例，说明编译器将代码转换为您认为将要执行的操作，或者仅是根据您的知识进行猜测？ （我会有相同的猜测，但我真的很想看看证明）
\ $ \ endgroup \ $
–马克·安德烈（Marc-Andre）
16年4月4日在14:58
\ $ \ begingroup \ $
原始代码“ compile”生成的字节代码可能确实具有嵌套的StringBuilder调用，因此此答案是正确的。如今，当字节码经历多个优化级别等时，发生的事情很难预测。无论如何，此答案都包含很好的建议。
\ $ \ endgroup \ $
–rolfl
16年4月4日在15:22
#6 楼
我将假设您这样做是为了学习更多Java，而不是像某个受薪雇员那样的实际项目。对于初学者，其他人已经告诉过您有关大小错误的信息。
我将在这里成为一个异端，并且说，由于您正在学习，因此请使用递归计算每次调用。
这将是一种不错的第一种递归方法，并且因为它是用于学习的，只要不怕速度，谁会关心速度。是吗？
它应该做的是计算将是什么索引（当然，通过调用size（）），然后告诉add（Object，int）将其添加到何处。
add(Object item) {
int index = size() - 1; // assumes zero-indexing
add(item, index);
}
每个人都清楚这是怎么回事。
我们都知道数组的最后一个元素是
array.length - 1，所以这对任何人都不足为奇。现在，在您完成Philipp的绝妙建议后，将其设为通用，并实现接口。我会对此加以补充，并建议学习有关注释，例如@NonNull注释。即使您不会自己大量使用它们，这些知识也可能很不错。
对于StringBuilder来说，很好地了解其工作原理，不仅是因为它更快，而且更重要的是，因为如果您只是在学习，那么很可能是您第一次与Builder模式会面，您将学会爱上第二次会议，即在其构造函数中看到带有14个String参数的类。 （该代码已外包到R'Lyeh中的深处。）
那时，您将知道该怎么做并有了更好的理解。
让我很伤心的一件事尽管您还没有添加任何Javadocs。 Javadocs是有关Java的最好的东西之一，它使竞争的平台在涉及文档方面加紧了工作。您确实应该学习如何编写它们。 Oracle有指南
其他所有内容已经被说过n次了，所以我不再赘述。
#7 楼
我认为您的remove函数可能只是一个很小的错误。不会在最后一个元素上调用.getNext().getNext给您一个NullPointerException，而您在其中调用.getNext()上的Null吗？
评论
\ $ \ begingroup \ $
+1表示公共无效add（对象数据）{add（data，size）; ……优雅而有效
\ $ \ endgroup \ $
– Aneesh K
15年2月27日在14:51