Преобразование одноуровневого списка в двусвязный список

Question

Прежде всего, я искал, и я не могу найти ничего, что помогло бы мне лучше понять, как реализовать двойной список. Я также скажу, что это для задания, которое у меня есть, и я не ожидаю, что кто-то просто сделает это за меня. С учетом сказанного, у меня есть рабочий код для отдельного связанного списка (линейный), который добавляет, удаляет, получает размер, очищает и т. Д. ... и я хочу реализовать реализацию двойного связывания в этом коде.

Из чего я понимаю, это должно быть довольно прямолинейным. Тем не менее, моя книга не вникает в очень подробные сведения об этом и дает очень мало для примера. Мне сложно представить, как это реализовать. Я понимаю, что в одном единственном списке предыдущий узел указывает только на следующий узел, требуя, чтобы вы проходили весь список в любое время, когда хотите удалить или добавить что-либо. В двусвязном списке он должен проходить с конца, ближайшего к узлу, с которым вы работаете. Пожалуйста, исправьте меня, если мое понимание неверно.

Вот фрагмент кода, который я до сих пор модифицировал.

private class Node 
{ 
    private T data; 
    private Node next; 
    private Node previous; 



    private Node(T dataPortion) 
    { 
     this(dataPortion, null, null); 
    } 

    private Node(T dataPortion, Node nextNode, Node prevNode) 
    { 
     data = dataPortion; 
     next = nextNode; 
     previous = prevNode; 

    } 

Я добавил «частный узел предыдущий» для ссылки на предыдущий узел в списке и установить, что равно prevNode после предыдущего формата, который был в коде. Есть ли что-то еще в начальной настройке, что мне нужно сделать, прежде чем перейти к отдельным методам?

В каждом из моих методов я не уверен, что мне нужно сделать, чтобы использовать это для ссылки на предыдущий узел, а также на следующий, как в настоящее время. Может ли кто-нибудь помочь мне с этим, возможно, предоставив некоторый пример кода? Вот текущий метод добавления ссылки.

public boolean add(T newEntry) 
{ 
    Node newNode = new Node(newEntry); 

    if (isEmpty()) 
     firstNode = newNode; 
    else 
    { 
     Node lastNode = getNodeAt(numberOfEntries); 
     lastNode.setNextNode(newNode); 
    } 

    numberOfEntries++; 

    return true; 
} 

Редактировать: Добавлено множество и методы получения для предыдущего узла.

private Node getNextNode() 
    { 
     return next; 
    } 

    private Node getPrevNode() 
    { 
     return previous; 
    } 

    private void setNextNode(Node nextNode) 
    { 
     next = nextNode; 
    } 
    private void setPrevNode(Node prevNode) 
    { 
     previous = prevNode; 
    } 

Является ли это тем, что я должен добавить?

public boolean add(T newEntry) 
{ 
    Node newNode = new Node(newEntry); 


    if (isEmpty()) 
     firstNode = newNode; 
    else 
    { 
     Node lastNode = getNodeAt(numberOfEntries); 
     Node prevNode = getNodeAt(numberOfEntries -1); 
     lastNode.setNextNode(newNode); 
     newNode.setPrevNode(prevNode); 
    } 

    numberOfEntries++; 

    return true; 
} 

Answer 1

Вы сделали все правильно. Все, что вам нужно, это добавить newNode.setPreviousNode(lastNode)

Вы посмотрите на LinkedList для справки можно. Они хранят в списке два узла для справки first и last. С таким подходом он позволяет вам не перебирать весь список в add методом с функцией getNodeAt.

Implementatopn метода надстройкой из LinkedList

void linkLast(E e) { 
    final Node<E> l = last; 
    final Node<E> newNode = new Node<>(l, e, null); 
    last = newNode; 
    if (l == null) 
     first = newNode; 
    else 
     l.next = newNode; 
    size++; 
    modCount++; 
} 

Answer 2

public boolean add(T newEntry) 
{ 
    Node newNode = new Node(newEntry); 
    newNode.previous = this; 
    newNode.next = next; 
    next = newNode; 
    numberOfEntries++; 
    return true; 
} 

Главное, что вам не нужно знать, что делает остальная часть структуры данных. Вам даже не нужно знать, что есть другие узлы. Вы просто укажете узлу, чтобы добавить этот узел и обновить ссылки. Или удалите этот узел, удалив ссылки на него.

public void remove() { 
    if (next != null) next.previous = previous; 
    if (previous != null) previous.next = next; 
    numberofEntries--; 
}