- 单向链表示意图：
- 单向链表实现代码：
- 测试：
- 结果：
以下是单链表相对于双链表的优缺点。
优点
（1) 只有一个指向下一个节点的指针。
（2) 单向链表增加删除节点简单。遍历时候不会死循环。
缺点
（1) 只能从头到尾遍历。只能找到后继，无法找到前驱，也就是只能前进。
import java.util.Arrays; import java.util.Iterator; import java.util.NoSuchElementException; import java.util.Spliterator; import java.util.function.Consumer; public class SingleLinkedList测试：implements Iterable { public int size; private Node head = null; private Node tail = null; private class Node { public T value; public Node nexNode; public Node(T value, Node next) { this.value = value; this.nexNode = next; } } public SingleLinkedList() { this.size = 0; } public SingleLinkedList(T value) { this.head = new Node(value, null); this.tail = head; size++; } public void add(T value) { if (size != 0) { Node node = new Node(value, null); tail.nexNode = node; tail = tail.nexNode; } else { this.head = new Node(value, null); this.tail = head; } size++; } public void addToHead(T value) { if (size != 0) { Node node = new Node(value, head); head = node; } else { this.head = new Node(value, null); this.tail = head; } size++; } public void addToTail(T value) { add(value); } public T get(int index) { return getIndexNode(index).value; } public void insert(int index, T value) { if (index < 0 || index >= size) { throw new IndexOutOfBoundsException("索引越界"); } if (index == 0) { addToHead(value); } else if (index == size - 1) { addToTail(value); } else { Node beforeNode = getIndexNode(index - 1); Node afterNode = getIndexNode(index); Node insertNode = new Node(value, afterNode); beforeNode.nexNode = insertNode; size++; } } public void clear() { //每一个结点的value和指向的前结点和后结点都置为null,防止内存溢出，有益GC回收 for (Node x = head; x != null; ) { Node next = x.nexNode; x.value = null; x.nexNode = null; x = next; } // 将底层数组所有元素赋为null head = tail = null; size = 0; } public void remove(int index) { if (index < 0 || index >= size) { throw new IndexOutOfBoundsException("索引越界"); } if (index == 0) { head.nexNode = null; Node afterNode = getIndexNode(index + 1); } else if (index == size - 1) { Node beforeNode = getIndexNode(index - 1); beforeNode.nexNode = null; } else { Node beforeNode = getIndexNode(index - 1); Node afterNode = getIndexNode(index + 1); Node removetNode = getIndexNode(index); removetNode.nexNode = null; beforeNode.nexNode = afterNode; } size--; } public boolean contains(T value) { if (null == value) { return false; } Node currentNode = head; for (int i = 0; i < size; i++) { if (value.equals(currentNode.value)) { return true; } currentNode = currentNode.nexNode; } return false; } public Node getIndexNode(int index) { if (index < 0 || index >= size) { throw new IndexOutOfBoundsException("索引越界"); } //根据index大小来确定从头部查还是尾部查，以增加查询速度 Node currentNode = head; for (int i = 0; i < size && currentNode != null; i++) { if (i == index) { return currentNode; } currentNode = currentNode.nexNode; } return null; } @Override public String toString() { String[] array = new String[size]; Node currentNode = head; for (int i = 0; i < size; i++) { array[i] = String.valueOf(currentNode.value); currentNode = currentNode.nexNode; } return Arrays.toString(array); } //此内部类用于实现迭代器，使得DoublieLinkedList能够通过Iterator来遍历 class SingleLinkedListIterator implements Iterator { Node cuerrentNode; public SingleLinkedListIterator(Node head) { if (head == null) { throw new NullPointerException(); } cuerrentNode = head; } @Override public boolean hasNext() { return cuerrentNode != null; } @Override public T next() { if (cuerrentNode == null) { throw new NoSuchElementException(); } Node node = cuerrentNode; cuerrentNode = node.nexNode; return node.value; } } @Override public Iterator iterator() { return new SingleLinkedListIterator(head); } @Override public void forEach(Consumer action) { Iterable.super.forEach(action); } @Override public Spliterator spliterator() { return Iterable.super.spliterator(); } }
SingleLinkedList结果：d = new SingleLinkedList<>(); d.add(1); d.add(2); d.add(3); d.add(4); d.add(5); d.add(6); //指定位置插入 d.insert(2, 222); //头部插入 d.addToHead(111); //尾部插入 d.addToTail(999); System.out.println("链表：" + d.toString()); //获取大小 System.out.println("链表长度:" + d.size); //判断是否包含 System.out.println("判断是否包含222：" + d.contains(222)); //获取指定位置的元素 System.out.println("获取index是3的列表元素：" + d.get(3)); //删除指定位置的数据 d.remove(3); System.out.println("删除index是3后的链表：" + d.toString()); System.out.println("链表长度:" + d.size); System.out.println("遍历链表:"); for (Integer v : d) { System.out.println(v); } //清空链表 d.clear(); System.out.println("清空链表后长度:" + d.size);
链表：[111, 1, 2, 222, 3, 4, 5, 6, 999] 链表长度:9 判断是否包含222：true 获取index是3的列表元素：222 删除index是3后的链表：[111, 1, 2, 3, 4, 5, 6, 999] 链表长度:8 遍历链表: 111 1 2 3 4 5 6 999 清空链表后长度:0
