0

我目前正在上 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;

下面的代码是插入函数，我需要确保新插入的块连接但我在想办法让它连接两者时遇到了麻烦。

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;

    }
4

2 回答 2

1

您向每个包含其前一个节点的节点添加一个额外的节点字段

插入伪代码：

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
}
于 2014-03-06T22:30:07.730 回答
1

For doubly linked list, you need to add both head and tail fields in the class so that it maintains a doubly linked data structure.

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

To add a new node to the end of the linked list, you can do

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++;
}

Note that you also need to deal with the empty list case which is the first if clause. Also you can set next and prev references for tail when you add the node.

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

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;
}
于 2014-03-06T23:05:43.177 回答