什么是单向链表？单向链表基础操作

朴灿烈づ我的快乐病毒、 2023-10-10 17:11 28阅读 0赞

在计算机科学中，链表是数据元素的线性集合，其每个元素都指向下一个元素，元素存储上并不连续。链表可以分为单向链表和双向链表。

单向链表，每个元素只知道其下一个元素是谁。

双向链表，每个元素知道其上一个元素和下一个元素。

循环链表，通常的链表尾节点 tail 指向的都是 null，而循环链表的 tail 指向的是头节点 head。链表内还有一种特殊的节点称为哨兵(Sentinel)节点，也叫做哑元( Dummy)节点，它不存储数据，通常用作头尾，用来简化边界判断。

### **单向链表** ###

根据单向链表的定义，首先定义一个存储 value 和 next 指针的类 Node，和一个描述头部节点的引用。

public class SinglyLinkedList {
        
        private Node head; // 头部节点
        
        private static class Node { // 节点类
            int value;
            Node next;
    
            public Node(int value, Node next) {            this.value = value;
                this.next = next;
            }
        }
    }

在上述代码中Node 定义为内部类，是为了对外隐藏实现细节，没必要让类的使用者关心 Node 结构定义为 static 内部类，是因为 Node 不需要与 SinglyLinkedList 实例相关，多个 SinglyLinkedList实例能共用 Node 类定义。下面演示单向链表的创建方法

头部添加（头插法）

public class SinglyLinkedList {
        // ...
        public void addFirst(int value) {
            this.head = new Node(value, this.head);
        }
    }

如果 this.head == null，新增节点指向 null，并作为新的 this.head。如果 this.head != null，新增节点指向原来的 this.head，并作为新的 this.head。**注意赋值操作执行顺序是从右到左**

### **尾部添加** ###

public class SinglyLinkedList {
        // ...
        private Node findLast() {
            if (this.head == null) {
                return null;
            }
            Node curr;
            for (curr = this.head; curr.next != null; ) {
                curr = curr.next;
            }
            return curr;
        }
        
        public void addLast(int value) {
            Node last = findLast();
            if (last == null) {
                addFirst(value);
                return;
            }
            last.next = new Node(value, null);
        }
    }

注意，找最后一个节点，终止条件是 curr.next == null ，分成两个方法是为了代码清晰，而且 findLast() 之后还能复用。

### **尾部添加多个** ###

public class SinglyLinkedList {
        // ...
        public void addLast(int first, int... rest) {
            
            Node sublist = new Node(first, null);
            Node curr = sublist;
            for (int value : rest) {
                curr.next = new Node(value, null);
                curr = curr.next;
            }
            
            Node last = findLast();
            if (last == null) {
                this.head = sublist;
                return;
            }
            last.next = sublist;
        }
    }

先串成一串 sublist，再作为一个整体添加。  
**根据索引获取**

public class SinglyLinkedList {
        // ...
        private Node findNode(int index) {
            int i = 0;
            for (Node curr = this.head; curr != null; curr = curr.next, i++) {
                if (index == i) {
                    return curr;
                }
            }
            return null;
        }
        
        private IllegalArgumentException illegalIndex(int index) {
            return new IllegalArgumentException(String.format("index [%d] 不合法%n", index));
        }
        
        public int get(int index) {
            Node node = findNode(index);
            if (node != null) {
                return node.value;
            }
            throw illegalIndex(index);
        }
    }

同样，分方法可以实现复用

插入

public class SinglyLinkedList {
        // ...
        public void insert(int index, int value) {
            if (index == 0) {
                addFirst(value);
                return;
            }
            Node prev = findNode(index - 1); // 找到上一个节点
            if (prev == null) { // 找不到
                throw illegalIndex(index);
            }
            prev.next = new Node(value, prev.next);
        }
    }

注意：插入包括下面的删除，都必须找到上一个节点。

删除

public class SinglyLinkedList {
        // ...
        public void remove(int index) {
            if (index == 0) {
                if (this.head != null) {
                    this.head = this.head.next;
                    return;
                } else {
                    throw illegalIndex(index);
                }
            }
            Node prev = findNode(index - 1);
            Node curr;
            if (prev != null && (curr = prev.next) != null) {
                prev.next = curr.next;
            } else {
                throw illegalIndex(index);
            }
        }
    }

第一个 if 块对应着 removeFirst 情况，最后一个 if 块对应着至少得两个节点的情况，不仅仅判断上一个节点非空，还要保证当前节点非空。