Реализация двусвязных списков

Question

Я просмотрел большинство тем здесь о списках с двойной связью, но до сих пор неясно, что будет дальше.

Я практикую книгу Гудрича и Тамассии на Java.Что касается двусвязных списков, пожалуйста, исправьте меня, если я ошибаюсь, он отличается от односвязного списка тем, что узел может быть вставлен в любом месте, а не только после заголовка или после хвоста, используя как следующий, так и предыдущий доступные узлы, аодносвязные списки, эта вставка в любом месте списка невозможна?

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

Например, Head<->A<->B<->C<->D<->E<->tail

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

Но пожалуйста, объясните.

Спасибо, Санджай

Answer 1

Предполагая, что класс узла такой:

public class Node {
    public Node next = null;
    public Node previous = null;
    public Object value;
}

Затем вы можете определить:

public void insertBefore(Node node, Node insert)
{
    Node previousNode = node.previous;

    insert.next = node;
    insert.previous = previousNode;

    if(previousNode != null)
        previousNode.next = insert;

    node.previous = insert;
}

и

public void insertAfter(Node node, Node insert)
{
    Node nextNode = node.next;

    insert.previous = node;
    insert.next = nextNode;

    if(nextNode!= null)
        nextNode.previous = insert;

    node.next = insert;
}

Надеюсь, что поможет

Answer 2

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

Это неправильно. Вы можете вставлять узлы в середине односвязного списка просто отлично. Единственное отличие состоит в том, что с двунаправленным списком легче ориентироваться, так как вы можете перемещаться по нему вперед и назад с любого заданного узла.

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

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

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

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

Answer 3

1. Вы также можете вставить в один связанный список.A-> B становится A-> C-> B, все, что вам нужно сделать, это изменить ссылку на следующий узел A и установить для C значение B.
2. По умолчанию имеет смысл вставлять после выбранного узла.
3. Вы устанавливаете следующий узел D на Z, предыдущий узел E на Z, следующий узел Z на E и предыдущий узел Z на D.

Надеюсь, я правильно понял ваши вопросы, они 'немного сбивает с толку.

Answer 4

Реализация двусвязного списка с использованием JAVA.Реализованные операции:

1. Вставить узел в DLL.
2. Удалить элемент n-й позиции из DLL.
3. Найти позицию элемента в DLL.
4. Извлечь все узлы из DLL.
5. Получить все узлы в обратном порядке из DLL.

6. Получить длину DLL.

   package com.config;
   
   import java.io.BufferedReader;
   import java.io.IOException;
   import java.io.InputStreamReader;
   
   public class DLL {
   
   public static void main(String args[]) throws NumberFormatException, IOException{
   
       int choice = 0;
       Node temp = null;
       Node head = null;
       boolean flage = true;
       int nodeCounter = 0;
   
       BufferedReader read = new BufferedReader(new InputStreamReader(System.in));
       do{
           Node node = new Node();
           System.out.println("Enter Node data");
           node.data = Integer.parseInt(read.readLine());
           if(flage){
               flage = false;
               head = node;
           }
           if(temp!=null){
               temp.next = node;
               node.prev = temp;
           }
           temp = node;
           nodeCounter++;
           System.out.println("Press 0 to quite for more node entry.");
           choice = Integer.parseInt(read.readLine());
       }while(choice != 0);
   
       temp.next = head;
       head.prev = temp;
       System.out.println("You have created "+nodeCounter+" nodes in doubly linked list");
   
       System.out.println("Retriving and Manipulation Operation perform : ");
       Node node = head;
       do{
           System.out.println("Press 1 for get all nodes from doubly linked list.");
           System.out.println("Press 2 for get all nodes in reverse from doubly linked list.");
           System.out.println("Press 3 for get length of doubly linked list.");
           System.out.println("Press 4 for remove nth node from doubly linked list.");
           System.out.println("Press 5 for find node in doubly linked list.");
           System.out.println("Press 0 for quite.");
           choice = Integer.parseInt(read.readLine());
   
           switch (choice) {
           case 1: Node.getAllNodes(node);
               break;
           case 2: Node.getAllNodesReverse(node);  
               break;
   
           case 3 : System.out.println("Length : "+Node.getDoublyLinkedListLength(node));
               break;
           case 4 : System.out.println("Enter Position to remove from DLL");
                   choice = Integer.parseInt(read.readLine());     
                   node = Node.removeNthNode(node, choice);    
                   break;
           case 5 :System.out.println("Enter Node data to find in DLL");
                   choice = Integer.parseInt(read.readLine());     
                   choice = Node.findNode(node, choice);
                   if(choice == 0){
                       System.out.println("Node Not Found in DLL");
                       choice = 1;
                   }else
                       System.out.println("Node Position : "+choice);  
           break;
           default:
               break;
           }
   
       }while(choice != 0);
   
   
   }
   
   
   }
   
   class Node{
   int data = 0;
   Node next = null;
   Node prev = null;
   
   
   public static void getAllNodes(Node head){
   int nodeCounter = 0;
   if(head!=null){
       Node tail = head.prev;
       while(head.next != tail.next ){
           nodeCounter++;
           System.out.println(nodeCounter+". Node : "+head.data);
           head = head.next;
       }
       nodeCounter++;
       System.out.println(nodeCounter+". Node : "+head.data);
   }
   }
   
   public static int getDoublyLinkedListLength(Node head){
   int nodeCounter = 0;
   if(head!=null){
       Node tail = head.prev;
       while(head.next != tail.next ){
           nodeCounter++;
           head = head.next;
       }
       nodeCounter++;
   }
   return nodeCounter;
   }
   
   public static int findNode(Node head,int data){
   int nodeCounter = 0;
   boolean flage = false;
   if(head!=null){
       Node tail = head.prev;
       while(head.next != tail.next ){
           nodeCounter++;
           if(head.data == data){
               flage = true;
               break;
           }
           head = head.next;
       }
   }
   
   return flage ? nodeCounter : 0;
   }
   
   public static void getAllNodesReverse(Node head){
   if(head!= null){
       int nodeCounter = 0;
       Node tail = head.prev;
       while(tail.prev!= head.prev){
           nodeCounter++;
           System.out.println(nodeCounter+". Node : "+tail.data);
           tail = tail.prev;
       }
       nodeCounter++;
       System.out.println(nodeCounter+". Node : "+tail.data);
   }
   }
   
   public static Node removeNthNode(Node head, int removePosition){
   int length = getDoublyLinkedListLength(head);
   if(head!=null){
       int counter = 1;
   
       if(length >2){
           if(length+1 > removePosition && removePosition > 0){
               while(counter != removePosition){
                   counter++;
                   head = head.next;
               }
               head.prev.next = head.next;
               head.next.prev = head.prev;
           }else{
               System.out.println("Given Position not exist");
           }
       }else{
           System.out.println("At least two nodes must be in doubly linked list.");
       }
   }
   if(removePosition==1 || removePosition==length)
       return head.next;
   else
       return head;
   }
   }