Java 实现双向链表

Java 实现双向链表

双向链表示意图：

以下是双链表相对于单链表的优缺点。
优点
（1) 可以向前和向后遍历。
（2) 如果给出指向要删除的节点的指针，双向链表中的删除 *** 作会更有效率。
（3）我们可以在给定节点之前快速插入一个新节点。
在单向链表中，要删除一个节点，需要指向前一个节点的指针。为了获得这个前一个节点，有时会遍历列表。在双链表中，我们可以使用前一个指针获取前一个节点。

缺点
（1) 双链表的每个节点都需要额外的空间用于前一个指针。
（2) 所有的 *** 作都需要一个额外的指针来维护。例如，在插入时，我们需要同时修改前一个指针和后一个指针。

双向链表实现代码：

import java.util.Arrays;

public class DoublielinkedList {

    
    public int size;
    
    private Node head = null;
    
    private Node tail = null;

    private class Node {
        public T value;
        public Node preNode;
        public Node nexNode;

        public Node(T value, Node pre, Node next) {
            this.value = value;
            this.preNode = pre;
            this.nexNode = next;
        }
    }

    public DoublielinkedList() {
        this.size = 0;
    }

    public DoublielinkedList(T value) {
        this.head = new Node(value, null, null);
        this.tail = head;
        size++;
    }

    
    public void add(T value) {
        if (size != 0) {
            Node node = new Node(value, tail, null);
            tail.nexNode = node;
            tail = tail.nexNode;
        } else {
            this.head = new Node(value, null, null);
            this.tail = head;
        }
        size++;
    }

    
    public void addToHead(T value) {
        if (size != 0) {
            Node node = new Node(value, null, head);
            head.preNode = node;
            head = head.preNode;
        } else {
            this.head = new Node(value, null, 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, beforeNode, afterNode);
            beforeNode.nexNode = insertNode;
            afterNode.preNode = insertNode;
            size++;
        }
    }

    
    public void clear() {
        // 将底层数组所有元素赋为null
        head = null;
        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);
            afterNode.preNode = null;
        } else if (index == size - 1) {
            tail.preNode = null;
            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;
            removetNode.preNode = null;
            beforeNode.nexNode = afterNode;
            afterNode.preNode = beforeNode;
        }
        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大小来确定从头部查还是尾部查，以增加查询速度
        if (index < size / 2) {
            Node currentNode = head;
            for (int i = 0; i < size / 2 && currentNode != null; i++) {
                if (i == index) {
                    return currentNode;
                }
                currentNode = currentNode.nexNode;
            }
        } else {
            Node currentNode = tail;
            for (int i = size - 1; i >= size / 2 && currentNode != null; i--) {
                if (i == index) {
                    return currentNode;
                }
                currentNode = currentNode.preNode;
            }
        }
        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);
    }
}

测试：

public class MainServer {
    public static void main(String[] args) {
        DoublielinkedList d = new DoublielinkedList<>();
        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(d.contains(222));
        //获取指定位置的元素
        System.out.println(d.get(3));

        //删除指定位置的数据
        d.remove(3);
        System.out.println(d.toString());
        System.out.println(d.size);

        //清空链表
        d.clear();
        System.out.println(d.size);
    }
}

结果：

[111, 1, 2, 222, 3, 4, 5, 6, 999]
9
true
222
[111, 1, 2, 3, 4, 5, 6, 999]
8
0