set方法可以先通过获取原来index位置的节点，通过Node的getElement方法获取节点上的元素，在通过Node的setElement方法设置指定的元素到指定索引的节点上。
@Override public T set(int index, T element) { Node<T> node = getNodeByIndex(index); T oldElement = node.getElement(); node.setElement(element); return oldElement; } 复制代码
@Override public void add(int index, T element) { CheckUtils.checkIndex4Add(index,size); // 获取指定索引的前一个元素 Node<T> prevNode = getNodeByIndex(index - 1); Node<T> nextNode = getNodeByIndex(index); // 创建新的Node Node<T> newNode = new Node(); newNode.setElement(element); // 新创建的Node指向下一个元素 newNode.setNext(nextNode); // 指定索引前的元素指向新加入的元素 prevNode.setNext(newNode); size++; } 复制代码
remove (int index) - 删除元素
@Override public T remove(int index) { CheckUtils.checkIndex(index,size); Node<T> node = first; if (index == 0){ first.next = first.next.next; } else { Node<T> prev = getNodeByIndex(index - 1); node = prev.next; prev.next = node.next; } size --; return node.getElement(); } 复制代码
重写toString方法
@Override public String toString() { StringBuilder string = new StringBuilder(); string.append("LinkedList {size=").append(size).append(", ["); Node<T> node = first; for (int i = 0; i < size; i++) { if (i != 0) { string.append(", "); } string.append(node.element); node = node.next; } string.append("]}"); return string.toString(); } 复制代码
创建LinkedListTest，增加测试方法
public class LinkedListTest { List<Integer> linkedList = new LinkedList<>(); @Before public void init() { linkedList.add(1); linkedList.add(2); linkedList.add(3); linkedList.add(4); System.out.println("初始化：" + linkedList); } @Test public void add() { linkedList.add(11); linkedList.add(34); linkedList.add(78); linkedList.add(1,99); System.out.println("执行add方法后，" + linkedList); } @Test public void remove(){ linkedList.remove(0); System.out.println("执行remove方法删除索引0位置的元素后，" + linkedList); linkedList.remove(2); System.out.println("再次执行remove方法删除索引2位置的元素后，" + linkedList); } @Test public void indexOf(){ int i = linkedList.indexOf(3); System.out.println("执行indexOf，元素3位置的索引为：" + i); } } 复制代码
执行LinkedListTest测试类
虚拟头节点
为了统一所有节点的处理逻辑，可以在链表最前面增加一个虚拟的头节点，不存储任何数据
有了虚拟头节点，那么链表中的first就是虚拟头节点，虚拟头节点无论链表是否为空都存在，需要增加一个构造方法。
// 增加带有虚拟头节点的构造函数，不管链表中是否存在元素，都有虚拟头节点 public LinkedListWthDummyHead(){ first = new Node<T>(null,null); } 复制代码
//获取指定索引对应的元素 public Node getNodeByIndex(int index){ CheckUtils.checkIndex(index,size); // 从first的next节点开始寻找，虚拟头节点的下一个节点开始 Node<T> node = first.next; for (int i = 0; i < index; i++) { node = node.getNext(); } return node; } 复制代码
有了虚拟头节点之后，链表中的每一个节点都有前一个节点，没有虚拟头节点时索引为0的节点是没有前一个节点的，所有在获取指定位置的前一个节点时都要进行判断当前节点是否是第一个节点，所以可以对这些代码作统一的修改,无需再判断是否是第一个节点。
修改add方法
@Override public void add(int index, T element) { CheckUtils.checkIndex4Add(index,size); Node<T> prev = index == 0 ? first : getNodeByIndex(index - 1); prev.next = new Node<>(element,prev.next); size++; } 复制代码
修改remove方法
@Override public T remove(int index) { CheckUtils.checkIndex(index,size); Node<T> prev = index == 0 ? first : getNodeByIndex(index - 1); Node<T> node = prev.next; prev.next = node.next; size --; return node.element; } 复制代码
修改toString()方法
@Override public String toString() { StringBuilder string = new StringBuilder(); string.append("LinkedList {size=").append(size).append(", ["); Node<T> node = first.next; for (int i = 0; i < size; i++) { if (i != 0) { string.append(", "); } string.append(node.element); node = node.next; } string.append("]}"); return string.toString(); } 复制代码
创建一个测试类LinkedListWthDummyHeadTest
public class LinkedListWthDummyHeadTest { List<Integer> linkedList = new LinkedListWthDummyHead<>(); @Before public void init() { linkedList.add(1); linkedList.add(2); linkedList.add(3); linkedList.add(4); System.out.println("初始化：" + linkedList); } @Test public void add() { linkedList.add(11); linkedList.add(34); linkedList.add(78); linkedList.add(1,99); System.out.println("执行add方法后，" + linkedList); } @Test public void remove(){ linkedList.remove(0); System.out.println("执行remove方法删除索引0位置的元素后，" + linkedList); linkedList.remove(2); System.out.println("再次执行remove方法删除索引2位置的元素后，" + linkedList); } @Test public void indexOf(){ int i = linkedList.indexOf(3); System.out.println("执行indexOf，元素3位置的索引为：" + i); } } 复制代码
执行测试
