怎么用java代码实现双向链表

发布时间：2022-05-26 15:50:57 作者：iii
来源：亿速云阅读：156

怎么用Java代码实现双向链表

双向链表（Doubly Linked List）是一种常见的数据结构，它允许在链表中向前和向后遍历。与单向链表不同，双向链表的每个节点不仅包含指向下一个节点的指针，还包含指向前一个节点的指针。这使得双向链表在某些操作中比单向链表更加灵活和高效。

本文将详细介绍如何使用Java代码实现一个双向链表，并解释每个步骤的实现细节。

1. 定义节点类

首先，我们需要定义一个节点类（Node），它包含三个部分：

data：存储节点的数据。
prev：指向前一个节点的指针。
next：指向下一个节点的指针。

class Node<T> {
    T data;
    Node<T> prev;
    Node<T> next;

    // 构造函数
    public Node(T data) {
        this.data = data;
        this.prev = null;
        this.next = null;
    }
}

2. 定义双向链表类

接下来，我们定义一个双向链表类（DoublyLinkedList），它包含以下成员变量和方法：

head：指向链表的头节点。
tail：指向链表的尾节点。
size：链表的长度。

class DoublyLinkedList<T> {
    private Node<T> head;
    private Node<T> tail;
    private int size;

    // 构造函数
    public DoublyLinkedList() {
        this.head = null;
        this.tail = null;
        this.size = 0;
    }

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

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

3. 实现添加操作

3.1 在链表头部添加节点

在链表头部添加节点时，我们需要更新新节点的next指针指向当前的头节点，并更新当前头节点的prev指针指向新节点。最后，将新节点设置为新的头节点。

public void addFirst(T data) {
    Node<T> newNode = new Node<>(data);
    if (isEmpty()) {
        head = tail = newNode;
    } else {
        newNode.next = head;
        head.prev = newNode;
        head = newNode;
    }
    size++;
}

3.2 在链表尾部添加节点

在链表尾部添加节点时，我们需要更新新节点的prev指针指向当前的尾节点，并更新当前尾节点的next指针指向新节点。最后，将新节点设置为新的尾节点。

public void addLast(T data) {
    Node<T> newNode = new Node<>(data);
    if (isEmpty()) {
        head = tail = newNode;
    } else {
        newNode.prev = tail;
        tail.next = newNode;
        tail = newNode;
    }
    size++;
}

3.3 在指定位置插入节点

在指定位置插入节点时，我们需要找到该位置的前一个节点和后一个节点，然后更新它们的指针以插入新节点。

public void add(int index, T data) {
    if (index < 0 || index > size) {
        throw new IndexOutOfBoundsException("Index: " + index + ", Size: " + size);
    }
    if (index == 0) {
        addFirst(data);
    } else if (index == size) {
        addLast(data);
    } else {
        Node<T> newNode = new Node<>(data);
        Node<T> current = head;
        for (int i = 0; i < index - 1; i++) {
            current = current.next;
        }
        newNode.next = current.next;
        newNode.prev = current;
        current.next.prev = newNode;
        current.next = newNode;
        size++;
    }
}

4. 实现删除操作

4.1 删除头节点

删除头节点时，我们需要将头节点的下一个节点设置为新的头节点，并更新新头节点的prev指针为null。

public T removeFirst() {
    if (isEmpty()) {
        throw new NoSuchElementException("List is empty");
    }
    T data = head.data;
    head = head.next;
    if (head == null) {
        tail = null;
    } else {
        head.prev = null;
    }
    size--;
    return data;
}

4.2 删除尾节点

删除尾节点时，我们需要将尾节点的前一个节点设置为新的尾节点，并更新新尾节点的next指针为null。

public T removeLast() {
    if (isEmpty()) {
        throw new NoSuchElementException("List is empty");
    }
    T data = tail.data;
    tail = tail.prev;
    if (tail == null) {
        head = null;
    } else {
        tail.next = null;
    }
    size--;
    return data;
}

4.3 删除指定位置的节点

删除指定位置的节点时，我们需要找到该节点的前一个节点和后一个节点，然后更新它们的指针以跳过该节点。

public T remove(int index) {
    if (index < 0 || index >= size) {
        throw new IndexOutOfBoundsException("Index: " + index + ", Size: " + size);
    }
    if (index == 0) {
        return removeFirst();
    } else if (index == size - 1) {
        return removeLast();
    } else {
        Node<T> current = head;
        for (int i = 0; i < index; i++) {
            current = current.next;
        }
        current.prev.next = current.next;
        current.next.prev = current.prev;
        size--;
        return current.data;
    }
}

5. 实现查找操作

5.1 查找指定位置的节点

查找指定位置的节点时，我们可以从头节点开始遍历链表，直到找到目标节点。

public T get(int index) {
    if (index < 0 || index >= size) {
        throw new IndexOutOfBoundsException("Index: " + index + ", Size: " + size);
    }
    Node<T> current = head;
    for (int i = 0; i < index; i++) {
        current = current.next;
    }
    return current.data;
}

5.2 查找包含指定数据的节点

查找包含指定数据的节点时，我们可以从头节点开始遍历链表，直到找到包含目标数据的节点。

public boolean contains(T data) {
    Node<T> current = head;
    while (current != null) {
        if (current.data.equals(data)) {
            return true;
        }
        current = current.next;
    }
    return false;
}

6. 实现遍历操作

6.1 从前向后遍历链表

从前向后遍历链表时，我们可以从头节点开始，依次访问每个节点的next指针，直到到达尾节点。

public void traverseForward() {
    Node<T> current = head;
    while (current != null) {
        System.out.print(current.data + " ");
        current = current.next;
    }
    System.out.println();
}

6.2 从后向前遍历链表

从后向前遍历链表时，我们可以从尾节点开始，依次访问每个节点的prev指针，直到到达头节点。

public void traverseBackward() {
    Node<T> current = tail;
    while (current != null) {
        System.out.print(current.data + " ");
        current = current.prev;
    }
    System.out.println();
}

7. 测试双向链表

最后，我们可以编写一个简单的测试程序来验证双向链表的实现是否正确。

public class Main {
    public static void main(String[] args) {
        DoublyLinkedList<Integer> list = new DoublyLinkedList<>();

        list.addFirst(1);
        list.addLast(3);
        list.add(1, 2);

        System.out.println("链表长度: " + list.size());
        System.out.print("从前向后遍历: ");
        list.traverseForward();
        System.out.print("从后向前遍历: ");
        list.traverseBackward();

        System.out.println("删除头节点: " + list.removeFirst());
        System.out.println("删除尾节点: " + list.removeLast());

        System.out.println("链表长度: " + list.size());
        System.out.print("从前向后遍历: ");
        list.traverseForward();
    }
}

8. 总结

通过以上步骤，我们成功地实现了一个双向链表。双向链表在插入、删除和遍历操作中具有较高的灵活性，尤其是在需要频繁进行双向遍历的场景中，双向链表比单向链表更加高效。希望本文能够帮助你理解并掌握双向链表的实现方法。