Java实现双端链表LinkedList

Java实现双端链表LinkedList的完整攻略

双端链表LinkedList介绍

双端链表LinkedList是链表的一种，除了拥有节点指向下一个节点的指针外，还拥有指向上一个节点的指针，这样可以双向遍历链表。常用的操作包括插入、删除、获取和遍历。

实现步骤

1. 定义节点类

节点类用来表示链表的一个节点，包含节点的值(value)、下一个节点(next)、上一个节点(previous)。

public class Node<T> {
    T value;
    Node<T> next;
    Node<T> previous;

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

2. 定义LinkedList类

LinkedList类包含链表的头节点(head)和尾节点(tail)以及链表的长度(size)。

public class LinkedList<T> {
    Node<T> head;
    Node<T> tail;
    int size;

    // 构造方法
    public LinkedList() {
        head = null;
        tail = null;
        size = 0;
    }

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

    // 获取链表的长度
    public int size() {
        return size;
    }

    // 在链表头部插入节点
    public void addFirst(T value) {
        Node<T> newNode = new Node<T>(value);
        if (isEmpty()) {
            head = newNode;
            tail = head;
        } else {
            newNode.next = head;
            head.previous = newNode;
            head = newNode;
        }
        size++;
    }

    // 在链表尾部插入节点
    public void addLast(T value) {
        Node<T> newNode = new Node<T>(value);
        if (isEmpty()) {
            head = newNode;
            tail = head;
        } else {
            tail.next = newNode;
            newNode.previous = tail;
            tail = newNode;
        }
        size++;
    }

    // 删除链表头部节点
    public void removeFirst() {
        if (!isEmpty()) {
            if (head == tail) {
                head = null;
                tail = null;
            } else {
                head = head.next;
                head.previous = null;
            }
            size--;
        }
    }

    // 删除链表尾部节点
    public void removeLast() {
        if (!isEmpty()) {
            if (head == tail) {
                head = null;
                tail = null;
            } else {
                tail = tail.previous;
                tail.next = null;
            }
            size--;
        }
    }

    // 获取链表头部节点的值
    public T getFirst() {
        if (!isEmpty()) {
            return head.value;
        } else {
            return null;
        }
    }

    // 获取链表尾部节点的值
    public T getLast() {
        if (!isEmpty()) {
            return tail.value;
        } else {
            return null;
        }
    }

    // 遍历链表
    public void traverse() {
        if (!isEmpty()) {
            Node<T> current = head;
            while (current != null) {
                System.out.print(current.value + " ");
                current = current.next;
            }
            System.out.println();
        }
    }
}

示例说明

示例一

public static void main(String[] args) {
    LinkedList<Integer> linkedList = new LinkedList<Integer>();
    linkedList.addFirst(1);
    linkedList.addLast(2);
    linkedList.addFirst(3);
    linkedList.traverse(); // 输出 3 1 2
    linkedList.removeFirst();
    linkedList.traverse(); // 输出 1 2
    linkedList.removeLast();
    linkedList.traverse(); // 输出 1
    System.out.println(linkedList.getFirst()); // 输出 1
    System.out.println(linkedList.getLast()); // 输出 1
    System.out.println(linkedList.size()); // 输出 1
}

以上示例展示了如何创建一个整型的LinkedList链表，并拥有头插法、尾插法、删除头节点、删除尾节点、获取头节点的值、获取尾节点的值、获取链表长度、依次输出链表的值的功能。

示例二

public static void main(String[] args) {
    LinkedList<String> linkedList = new LinkedList<String>();
    linkedList.addLast("Java");
    linkedList.addFirst("is");
    linkedList.addLast("great");
    linkedList.traverse(); // 输出 is Java great
    linkedList.removeFirst();
    linkedList.addFirst("Programming");
    linkedList.traverse(); // 输出 Programming Java great
    System.out.println(linkedList.size()); // 输出 3
}

以上示例展示了如何创建一个字符串类型的LinkedList链表，并使用尾插法、头插法、删除头节点、在头部插入节点、依次输出链表节点的值及获取链表长度的功能。