如何将单链表更改为双链表？

Question

我目前正在上Java课，教授告诉我们，理解链接的一个好方法是制作双向链表。我做了一个单链表，但是我很难把它转换成双向链表。所以我想知道是否有人能给我任何建议，以确保我的最后一个号码与前一个号码相连？如果前面的数字和最后一个数字连接到null。这是代码的一部分，如果你想得到更多，只要问，我会发布。

用于添加元素等的代码。这是我试图让尾部连接到最后一个数字的尝试。

public void add(int element){

            Node n = new Node();
            n.setItem(element);
            n.setNext(head);
            head = n;
            >
            //The tail connected to the new number added.
            n.setItem(element);
            n.setBefore(tail);
            tail = n;

下面的代码是insert函数，我需要确保新插入的块连接，但我很难想出一种方法使它同时连接这两个块。

public void insert(int element, int position){

        int currentposition = 0;
        Node currentNode = head;

        //Traverse to the right position
        while(currentposition < position-1){

            currentposition++;
        } 
        Node n = new Node();
        n.setItem(element);
        n.setNext(currentNode.getNext());
        currentNode.setNext(n);

        //The previous number connecting to the new number
        currentNode = tail;

    }

Answer 1

对于双链接列表，您需要在类中添加head和tail字段，以便它保持双链接数据结构。

private Node<T> head = null;
private Node<T> tail = head;
private int size = 0;

要将新节点添加到链表的末尾，可以执行以下操作

public void add(T element) {
    Node<T> node = new Node<T>(element);
    Node<T> current = head;
    if(current == null) {
        current = node;
        head = tail = current;
    } else {
        tail.next = node;
        node.prev = tail;
        tail = node;
    }
    size++;
}

注意，您还需要处理第一个if子句的空列表情况。还可以在添加节点时为tail设置next和prev引用。

要将节点插入到列表的某个位置，您需要考虑到，如果指定的位置小于0或大于现有列表大小，则会发生错误，因为您无法插入具有出界索引的元素。所以你可以抛出异常。当插入的位置在0（head）或在size（尾部）时，您还需要将大小写分开。考虑到所有这些情况，解决办法是：

public void insert(T a, int position) {
    if (position < 0 || position > size)
        throw new IndexOutOfBoundsException();
    Node<T> node = new Node<T>(a);
    Node<T> temp;
    if(position == 0) {
        if(head == null)
            add(a);
        else {
            temp = head;
            head = node;
            node.next = temp;
            temp.prev = node;
        }
        return;
    } else if (position == size) {
        temp = tail;
        tail = node;
        temp.next = tail;
        tail.prev = temp;
        return;
    }

    Node<T> current = head;
    int i = 0;
    while (current != null && i < position-1) {
        current = current.next;
        i++;
    }

    temp = current.next;
    current.next = node;
    node.prev = current;
    node.next = temp;
    temp.prev = node;
}

Answer 2

您可以向保存其先前节点的每个节点添加一个额外的节点字段

插入伪码：

insert(Node n, index i) {
    currentIndex = 0
    currentNode = head
    while (currentIndex < i) {
      currentNode = currentNode.next
      currentIndex++
    }
    n.prev = currentNode
    n.next = currentNode.next
    currentNode.next = n
}