Рубрики

Дважды связанный список | Комплект 1 (Введение и вставка)

Мы настоятельно рекомендуем ссылаться на следующий пост в качестве предварительного условия этого поста.

Введение в связанный список
Вставка узла в односвязный список

A D oubly L подписали Спи (DLL) содержит дополнительный указатель, обычно называемый предыдущий указатель, вместе со следующим указателем и данными , которые есть в односвязный список.

Ниже приведено представление узла DLL на языке Си.

С

/ * Узел двусвязного списка * /

struct Node {

    int data;

    struct Node* next; // Указатель на следующий узел в DLL

    struct Node* prev; // Указатель на предыдущий узел в DLL

};

Джава

// Класс для двусвязного списка

public class DLL {

    Node head; // заголовок списка

  

    / * Узел двусвязного списка * /

    class Node {

        int data;

        Node prev;

        Node next;

  

        // Конструктор для создания нового узла

        // next и prev по умолчанию инициализируются как null

        Node(int d) { data = d; }

    }

}

python3

# Узел двусвязного списка

class Node:

    def __init__(self, next=None, prev=None, data=None):

        self.next = next # ссылка на следующий узел в DLL

        self.prev = prev # ссылка на предыдущий узел в DLL

        self.data = data

Ниже приведены преимущества / недостатки двусвязного списка перед односвязным списком.

Преимущества перед односвязным списком
1) DLL может быть пройдена как в прямом, так и в обратном направлении.
2) Операция удаления в DLL более эффективна, если указан указатель на удаляемый узел.
3) Мы можем быстро вставить новый узел перед данным узлом.
В односвязном списке для удаления узла необходим указатель на предыдущий узел. Чтобы получить этот предыдущий узел, иногда список обходят. В DLL мы можем получить предыдущий узел, используя предыдущий указатель.

Недостатки перед односвязным списком
1) Каждый узел библиотеки DLL требует дополнительного места для предыдущего указателя. Можно реализовать DLL с одним указателем (см. Это и это ).
2) Для выполнения всех операций требуется дополнительный указатель. Например, при вставке нам нужно изменить предыдущие указатели вместе со следующими указателями. Например, в следующих функциях для вставок в разных позициях нам нужно 1 или 2 дополнительных шага, чтобы установить предыдущий указатель.

вставка
Узел может быть добавлен четырьмя способами
1) Перед DLL
2) После данного узла.
3) В конце DLL
4) Перед данным узлом.

1) Добавьте узел спереди: (5 шагов процесса)
Новый узел всегда добавляется перед заголовком данного связанного списка. И вновь добавленный узел становится новым главой DLL. Например, если данный связанный список равен 10152025, и мы добавляем элемент 5 спереди, то связанный список становится 510152025. Давайте вызовем функцию, которая добавляет в начало списка функцию push (). Push () должен получить указатель на указатель головы, потому что push должен изменить указатель головы, чтобы он указывал на новый узел (см. Это )

Ниже приведены 5 шагов для добавления узла спереди.

С

/ * Дана ссылка (указатель на указатель) на заголовок списка

   и int, вставляет новый узел в начало списка. * /

void push(struct Node** head_ref, int new_data)

{

    / * 1. выделить узел * /

    struct Node* new_node = (struct Node*)malloc(sizeof(struct Node));

  

    / * 2. вставить данные * /

    new_node->data = new_data;

  

    / * 3. Сделать следующий из нового узла заголовком, а предыдущий - NULL * /

    new_node->next = (*head_ref);

    new_node->prev = NULL;

  

    / * 4. изменить prev головного узла на новый узел * /

    if ((*head_ref) != NULL)

        (*head_ref)->prev = new_node;

  

    / * 5. переместить голову, чтобы указать на новый узел * /

    (*head_ref) = new_node;

}

Джава

// Добавление узла в начало списка

public void push(int new_data)

{

    / * 1. выделить узел

    * 2. введите данные * /

    Node new_Node = new Node(new_data);

  

    / * 3. Сделать следующий из нового узла заголовком, а предыдущий - NULL * /

    new_Node.next = head;

    new_Node.prev = null;

  

    / * 4. изменить prev головного узла на новый узел * /

    if (head != null)

        head.prev = new_Node;

  

    / * 5. переместить голову, чтобы указать на новый узел * /

    head = new_Node;

}

python3

# Добавление узла в начале списка

def push(self, new_data):

  

    # 1 и 2: выделить узел и вставить данные

    new_node = Node(data = new_data)

  

    # 3. Сделать следующий из нового узла заголовком, а предыдущий - NULL

    new_node.next = self.head

    new_node.prev = None

  

    # 4. измените prev головного узла на новый узел

    if self.head is not None:

        self.head.prev = new_node

  

    # 5. переместить голову, чтобы указать на новый узел

    self.head = new_node 

  
# Этот код предоставлен jatinreaper

Четыре шага из вышеуказанных пяти шагов совпадают с 4 шагами, используемыми для вставки спереди в односвязный список . Единственный дополнительный шаг — изменить предыдущую голову.

2) Добавить узел после данного узла .: (7 шагов процесса)
Нам дан указатель на узел как prev_node, и новый узел вставляется после данного узла.

С

/ * Учитывая узел как prev_node, вставить новый узел после данного узла * /

void insertAfter(struct Node* prev_node, int new_data)

{

    / * 1. проверить, является ли данный prev_node NULL * /

    if (prev_node == NULL) {

        printf("the given previous node cannot be NULL");

        return;

    }

  

    / * 2. выделить новый узел * /

    struct Node* new_node = (struct Node*)malloc(sizeof(struct Node));

  

    / * 3. вставить данные * /

    new_node->data = new_data;

  

    / * 4. Сделать следующий из нового узла следующим за предыдущим узлом * /

    new_node->next = prev_node->next;

  

    / * 5. Сделать следующий из prev_node как new_node * /

    prev_node->next = new_node;

  

    / * 6. Сделать prev_node как предыдущий из new_node * /

    new_node->prev = prev_node;

  

    / * 7. Изменить предыдущий следующий узел new_node * /

    if (new_node->next != NULL)

        new_node->next->prev = new_node;

}

Джава

/ * Учитывая узел как prev_node, вставить новый узел после данного узла * /

public void InsertAfter(Node prev_Node, int new_data)

{

  

    / * 1. проверить, является ли данный prev_node NULL * /

    if (prev_Node == null) {

        System.out.println("The given previous node cannot be NULL ");

        return;

    }

  

    / * 2. выделить узел

    * 3. вставьте данные * /

    Node new_node = new Node(new_data);

  

    / * 4. Сделать следующий из нового узла следующим за предыдущим узлом * /

    new_node.next = prev_Node.next;

  

    / * 5. Сделать следующий из prev_node как new_node * /

    prev_Node.next = new_node;

  

    / * 6. Сделать prev_node как предыдущий из new_node * /

    new_node.prev = prev_Node;

  

    / * 7. Изменить предыдущий следующий узел new_node * /

    if (new_node.next != null)

        new_node.next.prev = new_node;

}

python3

# Учитывая узел как prev_node, вставьте
# новый узел после данного узла

  

def insertAfter(self, prev_node, new_data):

  

        # 1. проверить, является ли данный prev_node NULL

        if prev_node is None:

            print("This node doesn't exist in DLL")

            return

  

        # 2. выделить узел & 3. положить в данные

        new_node = Node(data = new_data)

  

        # 4. Сделать следующий из нового узла следующим за предыдущим

        new_node.next = prev_node.next

  

        # 5. Сделать следующий из prev_node как new_node

        prev_node.next = new_node

  

        # 6. Сделайте prev_node как предыдущий из new_node

        new_node.prev = prev_node

  

        # 7. Изменить предыдущий из следующего узла new_node * /

        if new_node.next is not None:

            new_node.next.prev = new_node

  
# Этот код предоставлен jatinreaper

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

3) Добавить узел в конце: (7 шагов процесса)
Новый узел всегда добавляется после последнего узла данного связанного списка. Например, если заданная DLL является 510152025, и мы добавляем элемент 30 в конце, тогда DLL становится 51015202530.
Поскольку Связанный список обычно представлен его заголовком, мы должны пройти по списку до конца и затем изменить следующий из последнего узла на новый узел.

Ниже приведены 7 шагов для добавления узла в конце.

С

/ * Дана ссылка (указатель на указатель) на голову

   DLL и int, добавляет новый узел в конце * /

void append(struct Node** head_ref, int new_data)

{

    / * 1. выделить узел * /

    struct Node* new_node = (struct Node*)malloc(sizeof(struct Node));

  

    struct Node* last = *head_ref; / * используется на шаге 5 * /

  

    / * 2. вставить данные * /

    new_node->data = new_data;

  

    / * 3. Этот новый узел будет последним узлом, поэтому

          сделать следующее как NULL * /

    new_node->next = NULL;

  

    / * 4. Если Связанный список пуст, тогда создайте новый

          узел как голова * /

    if (*head_ref == NULL) {

        new_node->prev = NULL;

        *head_ref = new_node;

        return;

    }

  

    / * 5. Остальной ход до последнего узла * /

    while (last->next != NULL)

        last = last->next;

  

    / * 6. Изменить следующий из последнего узла * /

    last->next = new_node;

  

    / * 7. Сделать последний узел как предыдущий из нового узла * /

    new_node->prev = last;

  

    return;

}

Джава

// Добавить узел в конец списка

void append(int new_data)

{

    / * 1. выделить узел

     * 2. введите данные * /

    Node new_node = new Node(new_data);

  

    Node last = head; / * используется на шаге 5 * /

  

    / * 3. Этот новый узел будет последним узлом, поэтому

     * сделать следующее как NULL * /

    new_node.next = null;

  

    / * 4. Если Связанный список пуст, тогда создайте новый

     * узел как голова * /

    if (head == null) {

        new_node.prev = null;

        head = new_node;

        return;

    }

  

    / * 5. Остальной ход до последнего узла * /

    while (last.next != null)

        last = last.next;

  

    / * 6. Изменить следующий из последнего узла * /

    last.next = new_node;

  

    / * 7. Сделать последний узел как предыдущий из нового узла * /

    new_node.prev = last;

}

python3

# Добавить узел в конце DLL

def append(self, new_data):

  

        # 1. выделить узел 2. положить в данные

        new_node = Node(data = new_data)

        last = self.head

  

        # 3. Этот новый узел будет

        # последний узел, поэтому сделайте следующий из него как NULL

        new_node.next = None

  

        # 4. Если связанный список пуст, то

        # сделать новый узел головой

        if self.head is None:

            new_node.prev = None

            self.head = new_node

            return

  

        # 5. Остальное пройти до последнего узла

        while (last.next is not None):

            last = last.next

  

        # 6. Изменить следующий из последнего узла

        last.next = new_node

        # 7. Сделать последний узел как предыдущий из нового узла * /

        new_node.prev = last

  
# Этот код предоставлен jatinreaper

Шесть из вышеуказанных 7 шагов совпадают с 6 шагами, используемыми для вставки после данного узла в односвязный список . Один дополнительный шаг необходим для изменения предыдущего указателя нового узла.

4) Добавить узел перед данным узлом:

меры
Пусть указатель на данный узел будет next_node, а данные нового узла будут добавлены как new_data.

  1. Проверьте, является ли next_node NULL или нет. Если это NULL, вернитесь из функции, потому что любой новый узел не может быть добавлен до NULL
  2. Выделите память для нового узла, пусть он будет называться new_node
  3. Установите new_node-> data = new_data
  4. Установить предыдущий указатель этого new_node как предыдущий узел next_node, new_node-> prev = next_node-> prev
  5. Установить предыдущий указатель next_node как new_node, next_node-> prev = new_node
  6. Установить следующий указатель этого new_node как next_node, new_node-> next = next_node;
  7. Если предыдущий узел new_node не равен NULL, тогда установите следующий указатель этого предыдущего узла как new_node, new_node-> prev-> next = new_node
  8. Иначе, если prev для new_node равен NULL, это будет новый головной узел. Итак, make (* head_ref) = new_node.

Ниже приведена реализация вышеуказанного подхода:

C ++

// Полная рабочая программа на C, демонстрирующая все
// вставка перед данным узлом
#include <stdio.h> 
#include <stdlib.h> 

  
// Узел связанного списка

struct Node { 

    int data; 

    struct Node* next; 

    struct Node* prev; 

}; 

  
/ * Дана ссылка (указатель на указатель) на заголовок списка
и int, вставляет новый узел в начало списка. * /

void push(struct Node** head_ref, int new_data) 

    struct Node* new_node = (struct Node*)malloc(sizeof(struct Node)); 

  

    new_node->data = new_data; 

  

    new_node->next = (*head_ref); 

    new_node->prev = NULL; 

  

    if ((*head_ref) != NULL) 

        (*head_ref)->prev = new_node; 

  

    (*head_ref) = new_node; 

  
/ * Учитывая узел как next_node, вставить новый узел перед данным узлом * /

void insertBefore(struct Node** head_ref, struct Node* next_node, int new_data) 

    / * 1. проверить, является ли данный next_node NULL * /

    if (next_node == NULL) { 

        printf("the given next node cannot be NULL"); 

        return

    

  

    / * 2. выделить новый узел * /

    struct Node* new_node = (struct Node*)malloc(sizeof(struct Node)); 

  

    / * 3. вставить данные * /

    new_node->data = new_data; 

  

    / * 4. Сделать prev нового узла как prev следующего узла * /

    new_node->prev = next_node->prev; 

  

    / * 5. Сделайте предысторию next_node как new_node * /

    next_node->prev = new_node; 

  

    / * 6. Сделать next_node следующим за new_node * /

    new_node->next = next_node; 

  

    / * 7. Изменить следующий из предыдущего узла new_node * /

    if (new_node->prev != NULL) 

        new_node->prev->next = new_node; 

    / * 8. Если преддверие new_node равно NULL, оно будет

       новый головной узел * /

    else

        (*head_ref) = new_node;

      

  
// Эта функция печатает содержимое связанного списка, начиная с данного узла

void printList(struct Node* node) 

    struct Node* last; 

    printf("\nTraversal in forward direction \n"); 

    while (node != NULL) { 

        printf(" %d ", node->data); 

        last = node; 

        node = node->next; 

    

  

    printf("\nTraversal in reverse direction \n"); 

    while (last != NULL) { 

        printf(" %d ", last->data); 

        last = last->prev; 

    

  
/ * Программа драйвера для проверки вышеуказанных функций * /

int main() 

    / * Начнем с пустого списка * /

    struct Node* head = NULL; 

    push(&head, 7); 

  

    push(&head, 1); 

  

    push(&head, 4); 

  

    // Вставляем 8 перед 1. Таким образом, связанный список становится 4-> 8-> 1-> 7-> NULL

    insertBefore(&head, head->next, 8); 

  

    printf("Created DLL is: "); 

    printList(head); 

  

    getchar(); 

    return 0; 


Выход:

Created DLL is: 
Traversal in forward direction 
 4  8  1  7 
Traversal in reverse direction 
 7  1  8  4 

Полная рабочая программа для проверки вышеуказанных функций.
Ниже приведена полная программа для проверки вышеуказанных функций.

C ++

// Полная рабочая программа на C ++ для
// демонстрируем все методы вставки
#include <bits/stdc++.h>

using namespace std;

  
// Узел связанного списка

class Node 

    public:

    int data; 

    Node* next; 

    Node* prev; 

}; 

  
/ * Дана ссылка (указатель на указатель) на заголовок списка
и int, вставляет новый узел в начало списка. * /

void push(Node** head_ref, int new_data) 

    / * 1. выделить узел * /

    Node* new_node = new Node(); 

  

    / * 2. вставить данные * /

    new_node->data = new_data; 

  

    / * 3. Сделать следующий из нового узла заголовком, а предыдущий - NULL * /

    new_node->next = (*head_ref); 

    new_node->prev = NULL; 

  

    / * 4. изменить prev головного узла на новый узел * /

    if ((*head_ref) != NULL) 

        (*head_ref)->prev = new_node; 

  

    / * 5. переместить голову, чтобы указать на новый узел * /

    (*head_ref) = new_node; 

  
/ * Учитывая узел как prev_node, вставить новый узел после данного узла * /

void insertAfter(Node* prev_node, int new_data) 

    / * 1. проверить, является ли данный prev_node NULL * /

    if (prev_node == NULL) 

    

        cout<<"the given previous node cannot be NULL"

        return

    

  

    / * 2. выделить новый узел * /

    Node* new_node = new Node();

  

    / * 3. вставить данные * /

    new_node->data = new_data; 

  

    / * 4. Сделать следующий из нового узла следующим за предыдущим узлом * /

    new_node->next = prev_node->next; 

  

    / * 5. Сделать следующий из prev_node как new_node * /

    prev_node->next = new_node; 

  

    / * 6. Сделать prev_node как предыдущий из new_node * /

    new_node->prev = prev_node; 

  

    / * 7. Изменить предыдущий следующий узел new_node * /

    if (new_node->next != NULL) 

        new_node->next->prev = new_node; 

  
/ * Дана ссылка (указатель на указатель) на голову
DLL и int, добавляет новый узел в конце * /

void append(Node** head_ref, int new_data) 

    / * 1. выделить узел * /

    Node* new_node = new Node(); 

  

    Node* last = *head_ref; / * используется на шаге 5 * /

  

    / * 2. вставить данные * /

    new_node->data = new_data; 

  

    / * 3. Этот новый узел будет последним узлом, поэтому

        сделать следующее как NULL * /

    new_node->next = NULL; 

  

    / * 4. Если Связанный список пуст, тогда создайте новый

        узел как голова * /

    if (*head_ref == NULL)

    

        new_node->prev = NULL; 

        *head_ref = new_node; 

        return

    

  

    / * 5. Остальной ход до последнего узла * /

    while (last->next != NULL) 

        last = last->next; 

  

    / * 6. Изменить следующий из последнего узла * /

    last->next = new_node; 

  

    / * 7. Сделать последний узел как предыдущий из нового узла * /

    new_node->prev = last; 

  

    return

  
// Эта функция печатает содержимое
// связанный список, начиная с данного узла

void printList(Node* node) 

    Node* last; 

    cout<<"\nTraversal in forward direction \n"

    while (node != NULL) 

    

        cout<<" "<<node->data<<" "

        last = node; 

        node = node->next; 

    

  

    cout<<"\nTraversal in reverse direction \n"

    while (last != NULL) 

    

        cout<<" "<<last->data<<" "

        last = last->prev; 

    

  
/ * Программа драйвера для проверки вышеуказанных функций * /

int main() 

    / * Начнем с пустого списка * /

    Node* head = NULL; 

  

    // Вставляем 6. Таким образом, связанный список становится 6-> NULL

    append(&head, 6); 

  

    // Вставить 7 в начале. Так

    // связанный список становится 7-> 6-> NULL

    push(&head, 7); 

  

    // Вставить 1 в начале. Так

    // связанный список становится 1-> 7-> 6-> NULL

    push(&head, 1); 

  

    // Вставить 4 в конце. Так связано

    // список становится 1-> 7-> 6-> 4-> NULL

    append(&head, 4); 

  

    // Вставить 8, после 7. Так связано

    // список становится 1-> 7-> 8-> 6-> 4-> NULL

    insertAfter(head->next, 8); 

  

    cout << "Created DLL is: "

    printList(head); 

  

    return 0; 

  
// Это код, предоставленный rathbhupendra

С

// Полная рабочая программа на C, демонстрирующая все методы вставки
#include <stdio.h>
#include <stdlib.h>

  
// Узел связанного списка

struct Node {

    int data;

    struct Node* next;

    struct Node* prev;

};

  
/ * Дана ссылка (указатель на указатель) на заголовок списка

   и int, вставляет новый узел в начало списка. * /

void push(struct Node** head_ref, int new_data)

{

    / * 1. выделить узел * /

    struct Node* new_node = (struct Node*)malloc(sizeof(struct Node));

  

    / * 2. вставить данные * /

    new_node->data = new_data;

  

    / * 3. Сделать следующий из нового узла заголовком, а предыдущий - NULL * /

    new_node->next = (*head_ref);

    new_node->prev = NULL;

  

    / * 4. изменить prev головного узла на новый узел * /

    if ((*head_ref) != NULL)

        (*head_ref)->prev = new_node;

  

    / * 5. переместить голову, чтобы указать на новый узел * /

    (*head_ref) = new_node;

}

  
/ * Учитывая узел как prev_node, вставить новый узел после данного узла * /

void insertAfter(struct Node* prev_node, int new_data)

{

    / * 1. проверить, является ли данный prev_node NULL * /

    if (prev_node == NULL) {

        printf("the given previous node cannot be NULL");

        return;

    }

  

    / * 2. выделить новый узел * /

    struct Node* new_node = (struct Node*)malloc(sizeof(struct Node));

  

    / * 3. вставить данные * /

    new_node->data = new_data;

  

    / * 4. Сделать следующий из нового узла следующим за предыдущим узлом * /

    new_node->next = prev_node->next;

  

    / * 5. Сделать следующий из prev_node как new_node * /

    prev_node->next = new_node;

  

    / * 6. Сделать prev_node как предыдущий из new_node * /

    new_node->prev = prev_node;

  

    / * 7. Изменить предыдущий следующий узел new_node * /

    if (new_node->next != NULL)

        new_node->next->prev = new_node;

}

  
/ * Дана ссылка (указатель на указатель) на голову

   DLL и int, добавляет новый узел в конце * /

void append(struct Node** head_ref, int new_data)

{

    / * 1. выделить узел * /

    struct Node* new_node = (struct Node*)malloc(sizeof(struct Node));

  

    struct Node* last = *head_ref; / * используется на шаге 5 * /

  

    / * 2. вставить данные * /

    new_node->data = new_data;

  

    / * 3. Этот новый узел будет последним узлом, поэтому

          сделать следующее как NULL * /

    new_node->next = NULL;

  

    / * 4. Если Связанный список пуст, тогда создайте новый

          узел как голова * /

    if (*head_ref == NULL) {

        new_node->prev = NULL;

        *head_ref = new_node;

        return;

    }

  

    / * 5. Остальной ход до последнего узла * /

    while (last->next != NULL)

        last = last->next;

  

    / * 6. Изменить следующий из последнего узла * /

    last->next = new_node;

  

    / * 7. Сделать последний узел как предыдущий из нового узла * /

    new_node->prev = last;

  

    return;

}

  
// Эта функция печатает содержимое связанного списка, начиная с данного узла

void printList(struct Node* node)

{

    struct Node* last;

    printf("\nTraversal in forward direction \n");

    while (node != NULL) {

        printf(" %d ", node->data);

        last = node;

        node = node->next;

    }

  

    printf("\nTraversal in reverse direction \n");

    while (last != NULL) {

        printf(" %d ", last->data);

        last = last->prev;

    }

}

  
/ * Сушилка для тестирования вышеуказанных функций * /

int main()

{

    / * Начнем с пустого списка * /

    struct Node* head = NULL;

  

    // Вставляем 6. Таким образом, связанный список становится 6-> NULL

    append(&head, 6);

  

    // Вставить 7 в начале. Таким образом, связанный список становится 7-> 6-> NULL

    push(&head, 7);

  

    // Вставить 1 в начале. Таким образом, связанный список становится 1-> 7-> 6-> NULL

    push(&head, 1);

  

    // Вставить 4 в конце. Таким образом, связанный список становится 1-> 7-> 6-> 4-> NULL

    append(&head, 4);

  

    // Вставляем 8 после 7. Таким образом, связанный список становится 1-> 7-> 8-> 6-> 4-> NULL

    insertAfter(head->next, 8);

  

    printf("Created DLL is: ");

    printList(head);

  

    getchar();

    return 0;

}

Джава

// Полная рабочая Java-программа для демонстрации всего

  
// Класс для двусвязного списка

public class DLL {

    Node head; // заголовок списка

  

    / * Узел двусвязного списка * /

    class Node {

        int data;

        Node prev;

        Node next;

  

        // Конструктор для создания нового узла

        // next и prev по умолчанию инициализируются как null

        Node(int d) { data = d; }

    }

  

    // Добавление узла в начало списка

    public void push(int new_data)

    {

        / * 1. выделить узел

        * 2. введите данные * /

        Node new_Node = new Node(new_data);

  

        / * 3. Сделать следующий из нового узла заголовком, а предыдущий - NULL * /

        new_Node.next = head;

        new_Node.prev = null;

  

        / * 4. изменить prev головного узла на новый узел * /

        if (head != null)

            head.prev = new_Node;

  

        / * 5. переместить голову, чтобы указать на новый узел * /

        head = new_Node;

    }

  

    / * Учитывая узел как prev_node, вставить новый узел после данного узла * /

    public void InsertAfter(Node prev_Node, int new_data)

    {

  

        / * 1. проверить, является ли данный prev_node NULL * /

        if (prev_Node == null) {

            System.out.println("The given previous node cannot be NULL ");

            return;

        }

  

        / * 2. выделить узел

        * 3. вставьте данные * /

        Node new_node = new Node(new_data);

  

        / * 4. Сделать следующий из нового узла следующим за предыдущим узлом * /

        new_node.next = prev_Node.next;

  

        / * 5. Сделать следующий из prev_node как new_node * /

        prev_Node.next = new_node;

  

        / * 6. Сделать prev_node как предыдущий из new_node * /

        new_node.prev = prev_Node;

  

        / * 7. Изменить предыдущий следующий узел new_node * /

        if (new_node.next != null)

            new_node.next.prev = new_node;

    }

  

    // Добавить узел в конец списка

    void append(int new_data)

    {

        / * 1. выделить узел

        * 2. введите данные * /

        Node new_node = new Node(new_data);

  

        Node last = head; / * используется на шаге 5 * /

  

        / * 3. Этот новый узел будет последним узлом, поэтому

        * сделать следующее как NULL * /

        new_node.next = null;

  

        / * 4. Если Связанный список пуст, тогда создайте новый

        * узел как голова * /

        if (head == null) {

            new_node.prev = null;

            head = new_node;

            return;

        }

  

        / * 5. Остальной ход до последнего узла * /

        while (last.next != null)

            last = last.next;

  

        / * 6. Изменить следующий из последнего узла * /

        last.next = new_node;

  

        / * 7. Сделать последний узел как предыдущий из нового узла * /

        new_node.prev = last;

    }

  

    // Эта функция печатает содержимое связанного списка, начиная с данного узла

    public void printlist(Node node)

    {

        Node last = null;

        System.out.println("Traversal in forward Direction");

        while (node != null) {

            System.out.print(node.data + " ");

            last = node;

            node = node.next;

        }

        System.out.println();

        System.out.println("Traversal in reverse direction");

        while (last != null) {

            System.out.print(last.data + " ");

            last = last.prev;

        }

    }

  

    / * Сушилка для тестирования вышеуказанных функций * /

    public static void main(String[] args)

    {

        / * Начнем с пустого списка * /

        DLL dll = new DLL();

  

        // Вставляем 6. Таким образом, связанный список становится 6-> NULL

        dll.append(6);

  

        // Вставить 7 в начале. Таким образом, связанный список становится 7-> 6-> NULL

        dll.push(7);

  

        // Вставить 1 в начале. Таким образом, связанный список становится 1-> 7-> 6-> NULL

        dll.push(1);

  

        // Вставить 4 в конце. Таким образом, связанный список становится 1-> 7-> 6-> 4-> NULL

        dll.append(4);

  

        // Вставляем 8 после 7. Таким образом, связанный список становится 1-> 7-> 8-> 6-> 4-> NULL

        dll.InsertAfter(dll.head.next, 8);

  

        System.out.println("Created DLL is: ");

        dll.printlist(dll.head);

    }

}

  
// Этот код предоставлен Sumit Ghosh

питон

# Полная рабочая программа Python, чтобы продемонстрировать все
# методы вставки

  
# Узел связанного списка

class Node:

  

    # Конструктор для создания нового узла

    def __init__(self, data):

        self.data = data

        self.next = None

        self.prev = None

  
# Класс для создания двусвязного списка

class DoublyLinkedList:

  

    # Конструктор для пустого двусвязного списка

    def __init__(self):

        self.head = None

  

    # Учитывая ссылку на заголовок списка и

    # integer вставляет новый узел в начало списка

    def push(self, new_data):

  

        # 1. Распределяет узел

        # 2. Поместите в него данные

        new_node = Node(new_data)

  

        # 3. Сделать следующий из нового узла в качестве головы и

        # предыдущий как None (уже None)

        new_node.next = self.head

  

        # 4. измените prev главного узла на new_node

        if self.head is not None:

            self.head.prev = new_node

  

        # 5. переместить голову, чтобы указать на новый узел

        self.head = new_node

  

    # Учитывая узел как prev_node, вставьте новый узел после

    # данный узел

    def insertAfter(self, prev_node, new_data):

  

        # 1. Проверьте, является ли данный prev_node None

        if prev_node is None:

            print "the given previous node cannot be NULL"

            return 

  

        # 2. выделить новый узел

        # 3. положить в данные

        new_node = Node(new_data)

  

        # 4. Сделать сеть из нового узла следующим за предыдущим узлом

        new_node.next = prev_node.next

  

        # 5. Сделайте prev_node как предыдущий из new_node

        prev_node.next = new_node

  

        # 6. Сделать задницу prev_node предыдущим из new_node

        new_node.prev = prev_node

  

        # 7. Изменить предыдущий из следующего узла new_nodes

        if new_node.next is not None:

            new_node.next.prev = new_node

  

    # Учитывая ссылку на главу DLL и целое число,

    # добавляет новый узел в конце

    def append(self, new_data):

  

        # 1. Распределяет узел

        # 2. Вставьте данные

        new_node = Node(new_data)

  

        # 3. Этот новый узел будет последним узлом,

        # так сделайте следующее как None

        new_node.next = None

  

        # 4. Если Связанный список пуст, сделайте

        # новый узел в качестве головы

        if self.head is None:

            new_node.prev = None

            self.head = new_node

            return 

  

        # 5. Остальное пройти до последнего узла

        last = self.head

        while(last.next is not None):

            last = last.next

  

        # 6. Изменить следующий из последнего узла

        last.next = new_node

  

        # 7. Сделать последний узел как предыдущий из нового узла

        new_node.prev = last

  

        return

  

    # Эта функция печатает содержимое связанного списка

    # начиная с данного узла

    def printList(self, node):

  

        print "\nTraversal in forward direction"

        while(node is not None):

            print " % d" %(node.data),

            last = node

            node = node.next

  

        print "\nTraversal in reverse direction"

        while(last is not None):

            print " % d" %(last.data),

            last = last.prev

  
# Драйверная программа для проверки вышеуказанных функций

  
# Начнем с пустого списка

llist = DoublyLinkedList()

  
# Вставить 6. Таким образом, список становится 6-> Нет

llist.append(6)

  
# Вставьте 7 в начале.
# Так что связанный список становится 7-> 6-> Нет

llist.push(7)

  
# Вставьте 1 в начале.
# Таким образом, связанный список становится 1-> 7-> 6-> Нет

llist.push(1)

  
# Вставьте 4 в конце.
# Таким образом, связанный список становится 1-> 7-> 6-> 4-> Нет

llist.append(4)

  
# Вставить 8, после 7.
# Таким образом, связанный список становится 1-> 7-> 8-> 6-> 4-> Нет

llist.insertAfter(llist.head.next, 8)

  

print "Created DLL is: ",

llist.printList(llist.head)

  
# Этот код предоставлен Nikhil Kumar Singh (nickzuck_007)

C #

// Полная рабочая программа на C # для демонстрации всего

using System; 

  
// Класс для двусвязного списка

public class DLL 

    Node head; // заголовок списка

  

    / * Узел двусвязного списка * /

    public class Node 

    

        public int data; 

        public Node prev; 

        public Node next; 

  

        // Конструктор для создания нового узла

        // next и prev по умолчанию инициализируются как null

        public Node(int d) 

        

            data = d;

        

    

  

    // Добавление узла в начало списка

    public void push(int new_data) 

    

        / * 1. выделить узел

        * 2. введите данные * /

        Node new_Node = new Node(new_data); 

  

        / * 3. Сделать следующий из нового узла как

        head и предыдущий как NULL * /

        new_Node.next = head; 

        new_Node.prev = null

  

        / * 4. изменить prev головного узла на новый узел * /

        if (head != null

            head.prev = new_Node; 

  

        / * 5. переместить голову, чтобы указать на новый узел * /

        head = new_Node; 

    

  

    / * Учитывая узел как prev_node, вставить

    новый узел после данного узла * /

    public void InsertAfter(Node prev_Node, int new_data) 

    

  

        / * 1. проверить, является ли данный prev_node NULL * /

        if (prev_Node == null)

        

            Console.WriteLine("The given previous node cannot be NULL "); 

            return

        

  

        / * 2. выделить узел

        * 3. вставьте данные * /

        Node new_node = new Node(new_data); 

  

        / * 4. Сделать следующий из нового узла следующим за предыдущим узлом * /

        new_node.next = prev_Node.next; 

  

        / * 5. Сделать следующий из prev_node как new_node * /

        prev_Node.next = new_node; 

  

        / * 6. Сделать prev_node как предыдущий из new_node * /

        new_node.prev = prev_Node; 

  

        / * 7. Изменить предыдущий следующий узел new_node * /

        if (new_node.next != null

            new_node.next.prev = new_node; 

    

  

    // Добавить узел в конец списка

    void append(int new_data) 

    

        / * 1. выделить узел

        * 2. введите данные * /

        Node new_node = new Node(new_data); 

  

        Node last = head; / * используется на шаге 5 * /

  

        / * 3. Этот новый узел собирается

            быть последним узлом, так

        * сделать следующее как NULL * /

        new_node.next = null

  

        / * 4. Если Связанный список пуст,

        затем сделайте новый * узел в качестве головы * /

        if (head == null

        

            new_node.prev = null

            head = new_node; 

            return

        

  

        / * 5. Остальной ход до последнего узла * /

        while (last.next != null

            last = last.next; 

  

        / * 6. Изменить следующий из последнего узла * /

        last.next = new_node; 

  

        / * 7. Сделать последний узел как предыдущий из нового узла * /

        new_node.prev = last; 

    

  

    // Эта функция печатает содержимое

    // связанный список, начиная с данного узла

    public void printlist(Node node) 

    

        Node last = null

        Console.WriteLine("Traversal in forward Direction"); 

        while (node != null) { 

            Console.Write(node.data + " "); 

            last = node; 

            node = node.next; 

        

        Console.WriteLine(); 

        Console.WriteLine("Traversal in reverse direction"); 

        while (last != null) { 

            Console.Write(last.data + " "); 

            last = last.prev; 

        

    

  

    / * Код водителя * /

    public static void Main(String[] args) 

    

        / * Начнем с пустого списка * /

        DLL dll = new DLL(); 

  

        // Вставляем 6. Таким образом, связанный список становится 6-> NULL

        dll.append(6); 

  

        // Вставить 7 в начале.

        // Таким образом, связанный список становится 7-> 6-> NULL

        dll.push(7); 

  

        // Вставить 1 в начале.

        // Таким образом, связанный список становится 1-> 7-> 6-> NULL

        dll.push(1); 

  

        // Вставить 4 в конце. Так связан список

        // становится 1-> 7-> 6-> 4-> NULL

        dll.append(4); 

  

        // Вставить 8, после 7. Итак, связанный список

        // становится 1-> 7-> 8-> 6-> 4-> NULL

        dll.InsertAfter(dll.head.next, 8); 

  

        Console.WriteLine("Created DLL is: "); 

        dll.printlist(dll.head); 

    

  
// Этот код предоставлен 29AjayKumar


Выход:

 Created DLL is:
Traversal in forward direction
 1  7  8  6  4
Traversal in reverse direction
 4  6  8  7  1

Также см. — Удалить узел в двойном списке ссылок.
Пожалуйста, пишите комментарии, если вы обнаружите что-то неправильное или вы хотите поделиться дополнительной информацией по обсуждаемой выше теме.

Рекомендуемые посты:

Дважды связанный список | Комплект 1 (Введение и вставка)

0.00 (0%) 0 votes