Java实现链表

单向链表 只有一个方向，结点只有一个后继指针 next 指向后面的节点。因此，链表这种数据结构通常在物理内存上是不连续的。我们习惯性地把第一个结点叫作头结点，链表通常有一个不保存任何值的 head 节点(头结点)，通过头结点我们可以遍历整个链表。尾结点通常指向 null。

单向链表代码简单实现：

public class SinglylinkedList {

    Node head;  //头节点，不存放数据

    private int size;  //节点长度


    private class Node {
        private T val;   //节点的数据
        private Node next;  //节点的引用，指向下一个节点

        public Node(T value) {
            this.val = value;
        }
    }

    public SinglylinkedList() {
        //初始化头结点
        head = new Node(null);
    }

    //添加节点
    public void add(T t) {
        Node temp = head;
        final Node node = new Node(t);
        size++;   //链表长度+1
        //如果节点为空,则添加为首节点
        if (temp.next == null) {
            temp.next = node;
            return;
        }
        while (temp.next != null) {
            temp = temp.next;
        }
        //添加节点
        temp.next = node;
    }

    //插入节点
    public boolean insert(int index, T t) {
        if (isEmpty() || index < 1 || index > size) {
            return false;
        }
        Node temp = head;
        final Node node = new Node(t);
        for (int i = 1; i < index; i++) {
            temp = temp.next;
        }
        //节点的插入
        node.next = temp.next;
        temp.next = node;
        size++;
        return true;
    }

    //删除节点
    public boolean delNode(int index) {
        //链表为空或者index不符合查询条件则返回false
        if (index < 1 || size == 0 || index > size) {
            return false;
        }
        Node temp = head;
        for (int i = 1; i < index; i++) {
            temp = temp.next;
        }
        //删除节点
        temp.next = temp.next.next;
        size--;
        return true;
    }

    //修改节点
    public boolean setNode(int index, T t) {
        //链表为空或者index不符合查询条件则返回false
        if (index < 1 || size == 0 || index > size) {
            return false;
        }
        Node temp = head;
        for (int i = 1; i < index; i++) {
            temp = temp.next;
        }
        //修改节点内容
        temp.next.val = t;
        return true;
    }

    //遍历链表
    public void traverse() {
        Node temp = head.next;
        while (temp != null) {
            System.out.println(temp.val);
            temp = temp.next;
        }
    }

    //获取首节点元素
    public T getFirst() {
        //链表为空,返回null
        if (size == 0) {
            return null;
        }
        Node temp = head;
        return temp.next.val;
    }

    //获取尾节点元素
    public T getLast() {
        if (size == 0) {
            return null;
        }
        Node temp = head;
        while (temp.next != null) {
            temp = temp.next;
        }
        return temp.val;
    }

    //获取第i个节点的元素
    public T getValue(int index) {
        //index不符合条件则返回false
        if (size == 0 || index < 1 || index > size) {
            return null;
        }
        Node temp = head;
        for (int i = 1; i < index; i++) {
            temp = temp.next;
        }
        return temp.next.val;
    }

    //判断链表是否为空
    public boolean isEmpty() {
        return size == 0;
    }

}

双向链表 包含两个指针，一个 pre 指向前一个节点，一个 next 指向后一个节点。

链表的头结点不存储数据，指向前驱结点的指针域值为null，指向后继结点的指针域指向第一个真正存储数据的结点

双向链表代码简单实现：

public class DoublylinkedList {
    //头节点，不存放数据
    Node head;
    private int size;  //节点长度

    private class Node {
        Node next;   //节点的引用，指向下一个节点
        Node pre;     //节点的引用，指向上一个节点
        T val;  //节点的数据

        public Node(T value) {
            this.val = value;
        }
    }

    public DoublylinkedList() {
        head = new Node(null);
    }

    //添加节点
    public void add(T t) {
        Node temp = head;
        final Node node = new Node(t);
        size++;  //链表长度＋1
        if (temp.next == null) {
            temp.next = node;
            node.pre = temp;
            return;
        }
        while (temp.next != null) {
            temp = temp.next;
        }
        temp.next = node;
        node.pre = temp;
    }

    //插入节点
    public boolean insert(int index, T t) {
        //链表为空或者index不符合查询条件则返回false
        if (size == 0 || index < 1 || index > size) {
            return false;
        }
        size++;
        Node temp = head;
        final Node node = new Node(t);
        //遍历到第index个节点
        for (int i = 1; i < index; i++) {
            temp = temp.next;
        }
        node.next = temp.next;
        temp.next.pre = node;
        temp.next = node;
        node.pre = temp;
        return true;
    }

    //删除节点
    public boolean delNode(int index) {
        //链表为空或者index不符合查询条件则返回false
        if (size == 0 || index < 1 || index > size) {
            return false;
        }
        Node temp = head;
        for (int i = 0; i < index; i++) {
            temp = temp.next;
        }
        //当size==index时则是删除尾节点,直接将倒数第二个节点的next改成null即可
        if (size == index) {
            size--;
            //删除节点
            temp.pre.next = null;
            return true;
        }
        size--;
        //删除节点
        temp.pre.next = temp.next;
        temp.next.pre = temp.pre;
        return true;
    }

    //修改节点数据
    public boolean setNode(int index, T t) {
        //链表为空或者index不符合查询条件则返回false
        if (size == 0 || index < 1 || index > size) {
            return false;
        }
        Node temp = head;
        for (int i = 0; i < index; i++) {
            temp = temp.next;
        }
        temp.val = t;
        return true;
    }

    //遍历链表
    public void traverse() {
        Node temp = head.next;
        while (temp != null) {
            System.out.println(temp.val);
            temp = temp.next;
        }
    }

    //获取首节点元素
    public T getFirst() {
        //链表为空,返回null
        if (size == 0) {
            return null;
        }
        Node temp = head;
        return temp.next.val;
    }

    //获取尾节点元素
    public T getLast() {
        //链表为空,返回null
        if (size == 0) {
            return null;
        }
        Node temp = head;
        while (temp.next != null) {
            temp = temp.next;
        }
        return temp.val;
    }

    //判断链表是否为空
    public boolean isEmpty() {
        return size == 0;
    }

    //获取第i个节点元素
    public T getValue(int index) {
        //链表为空或者index不符合查询条件则返回null
        if (size == 0 || index < 1 || index > size) {
            return null;
        }
        Node temp = head;
        for (int i = 1; i <= index; i++) {
            temp = temp.next;
        }
        return temp.val;
    }
}