链表常用操作的代码实现

以单链表为例，假设单链表的节点结构为

class Node {
  int data;
  Node next;
  public Node(int data) {
    this.data = data;
  }
}

则单链表的实现如下

package linkedList;

/**
 * @author sunyixuan
 */
public class SingleLinkedList {

    private Node dummyHead = new Node(0);

    int length = 0;

    /**
     * 往链表头部插入数据
     * 原链表：dummyHead -> node -> null
     * 插入数据后：dummyHead -> newNode -> node -> null
     *
     * @param data 待插入的数据
     */
    public void addHead(int data) {

        Node newNode = new Node(data);
        // 将新插入节点的下一个节点指向虚拟头节点的下一个节点
        newNode.next = dummyHead.next;
        // 将虚拟头节点的下一节点指向新插入的节点
        dummyHead.next = newNode;
        length++;
    }

    /**
     * 往链表尾部插入数据
     * 原链表：dummyHead -> node -> null
     * 插入数据后：dummyHead -> node -> newNode -> null
     *
     * @param data 待插入数据
     */
    public void addLast(int data) {

        Node newNode = new Node(data);

        Node temp = dummyHead;

        while (temp.next != null) {
            temp = temp.next;
        }
        temp.next = newNode;
        length++;
    }

    /**
     * 按索引位置插入数据
     *
     * @param index 索引位置
     * @param data  数据
     */
    public void addIndex(int index, int data) {

        if (index < 0 || index > length) {
            throw new IndexOutOfBoundsException();
        }

        Node newNode = new Node(data);

        Node temp = dummyHead;

        for (int i = 0; i < index; i++) {
            temp = temp.next;
        }
        newNode.next = temp.next;
        temp.next = newNode;
        length++;
    }

    /**
     * 删除所有给定值
     * @param data 给定值
     */
    public void remove(int data) {

        Node prev = dummyHead;
        Node temp = dummyHead.next;

        while (temp != null) {

            if (temp.data == data) {
                prev.next = temp.next;
                temp = temp.next;
                length--;
            } else {
                prev = temp;
                temp = temp.next;
            }
        }
    }

    public void print() {

        Node current = dummyHead.next;
        while (current != null) {
            System.out.print(current.data + " -> ");
            current = current.next;
        }
        System.out.println("null");
    }

    /**
     * 反转链表
     */
    public void revert() {

        Node prev = dummyHead.next;
        if (prev == null) {
            return;
        }
        Node current = dummyHead.next.next;

        Node next = null;

        prev.next = null;

        while (current != null) {

            next = current.next;

            current.next = prev;

            prev = current;
            current = next;
        }
        dummyHead.next = prev;
    }

    public static void main(String[] args) {

        SingleLinkedList linkedList = new SingleLinkedList();

        linkedList.addHead(1);
        linkedList.addLast(2);
        linkedList.addLast(3);

        linkedList.print();

        linkedList.revert();

        linkedList.print();

        linkedList.remove(2);

        linkedList.print();
    }
}