Двусвязный список | Набор 1 (Введение и вставка)

Опубликовано: 27 Января, 2022

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

Following is representation of a DLL node in C language.

C

/* Node of a doubly linked list */
struct Node {
    int data;
    struct Node* next; // Pointer to next node in DLL
    struct Node* prev; // Pointer to previous node in DLL
};

Java

// Class for Doubly Linked List
public class DLL {
    Node head; // head of list
 
    /* Doubly Linked list Node*/
    class Node {
        int data;
        Node prev;
        Node next;
 
        // Constructor to create a new node
        // next and prev is by default initialized as null
        Node(int d) { data = d; }
    }
}

Python3

# Node of a doubly linked list
class Node:
    def __init__(self, next=None, prev=None, data=None):
        self.next = next # reference to next node in DLL
        self.prev = prev # reference to previous node in DLL
        self.data = data

C#

// Class for Doubly Linked List
public class DLL {
    Node head; // head of list
 
    /* Doubly Linked list Node*/
    public class Node {
        public int data;
        public Node prev;
        public Node next;
 
        // Constructor to create a new node
        // next and prev is by default initialized as null
        Node(int d) { data = d; }
    }
}
 
// This code contributed by gauravrajput1

Ниже приведены преимущества / недостатки двусвязного списка по сравнению с односвязным списком.
Преимущества перед односвязным списком
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 должен изменить указатель головы, чтобы он указывал на новый узел (см. Это)

Following are the 5 steps to add node at the front.

C

/* Given a reference (pointer to pointer) to the head of a list
   and an int, inserts a new node on the front of the list. */
void push(struct Node** head_ref, int new_data)
{
    /* 1. allocate node */
    struct Node* new_node = (struct Node*)malloc(sizeof(struct Node));
 
    /* 2. put in the data  */
    new_node->data = new_data;
 
    /* 3. Make next of new node as head and previous as NULL */
    new_node->next = (*head_ref);
    new_node->prev = NULL;
 
    /* 4. change prev of head node to new node */
    if ((*head_ref) != NULL)
        (*head_ref)->prev = new_node;
 
    /* 5. move the head to point to the new node */
    (*head_ref) = new_node;
}

Java

// Adding a node at the front of the list
public void push(int new_data)
{
    /* 1. allocate node
    * 2. put in the data */
    Node new_Node = new Node(new_data);
 
    /* 3. Make next of new node as head and previous as NULL */
    new_Node.next = head;
    new_Node.prev = null;
 
    /* 4. change prev of head node to new node */
    if (head != null)
        head.prev = new_Node;
 
    /* 5. move the head to point to the new node */
    head = new_Node;
}

Python3

# Adding a node at the front of the list
def push(self, new_data):
 
    # 1 & 2: Allocate the Node & Put in the data
    new_node = Node(data = new_data)
 
    # 3. Make next of new node as head and previous as NULL
    new_node.next = self.head
    new_node.prev = None
 
    # 4. change prev of head node to new node
    if self.head is not None:
        self.head.prev = new_node
 
    # 5. move the head to point to the new node
    self.head = new_node
 
# This code is contributed by jatinreaper

C#

// Adding a node at the front of the list
public void push(int new_data)
{
   
    /* 1. allocate node
    * 2. put in the data */
    Node new_Node = new Node(new_data);
 
    /* 3. Make next of new node as head and previous as NULL */
    new_Node.next = head;
    new_Node.prev = null;
 
    /* 4. change prev of head node to new node */
    if (head != null)
        head.prev = new_Node;
 
    /* 5. move the head to point to the new node */
    head = new_Node;
}
 
// This code is contributed by aashish1995

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


C

/* Given a node as prev_node, insert a new node after the given node */
void insertAfter(struct Node* prev_node, int new_data)
{
    /*1. check if the given prev_node is NULL */
    if (prev_node == NULL) {
        printf("the given previous node cannot be NULL");
        return;
    }
 
    /* 2. allocate new node */
    struct Node* new_node = (struct Node*)malloc(sizeof(struct Node));
 
    /* 3. put in the data  */
    new_node->data = new_data;
 
    /* 4. Make next of new node as next of prev_node */
    new_node->next = prev_node->next;
 
    /* 5. Make the next of prev_node as new_node */
    prev_node->next = new_node;
 
    /* 6. Make prev_node as previous of new_node */
    new_node->prev = prev_node;
 
    /* 7. Change previous of new_node"s next node */
    if (new_node->next != NULL)
        new_node->next->prev = new_node;
}

Java

/* Given a node as prev_node, insert a new node after the given node */
public void InsertAfter(Node prev_Node, int new_data)
{
 
    /*1. check if the given prev_node is NULL */
    if (prev_Node == null) {
        System.out.println("The given previous node cannot be NULL ");
        return;
    }
 
    /* 2. allocate node
    * 3. put in the data */
    Node new_node = new Node(new_data);
 
    /* 4. Make next of new node as next of prev_node */
    new_node.next = prev_Node.next;
 
    /* 5. Make the next of prev_node as new_node */
    prev_Node.next = new_node;
 
    /* 6. Make prev_node as previous of new_node */
    new_node.prev = prev_Node;
 
    /* 7. Change previous of new_node"s next node */
    if (new_node.next != null)
        new_node.next.prev = new_node;
}

Python3

# Given a node as prev_node, insert
# a new node after the given node
 
def insertAfter(self, prev_node, new_data):
 
        # 1. check if the given prev_node is NULL
        if prev_node is None:
            print("This node doesn"t exist in DLL")
            return
 
        #2. allocate node  & 3. put in the data
        new_node = Node(data = new_data)
 
        # 4. Make next of new node as next of prev_node
        new_node.next = prev_node.next
 
        # 5. Make the next of prev_node as new_node
        prev_node.next = new_node
 
        # 6. Make prev_node as previous of new_node
        new_node.prev = prev_node
 
        # 7. Change previous of new_node"s next node */
        if new_node.next is not None:
            new_node.next.prev = new_node
 
#  This code is contributed by jatinreaper

C#

/* Given a node as prev_node, insert a new node after the given node */
public void InsertAfter(Node prev_Node, int new_data)
{
 
    /*1. check if the given prev_node is NULL */
    if (prev_Node == null) {
        Console.WriteLine("The given previous node cannot be NULL ");
        return;
    }
 
    /* 2. allocate node
    * 3. put in the data */
    Node new_node = new Node(new_data);
 
    /* 4. Make next of new node as next of prev_node */
    new_node.next = prev_Node.next;
 
    /* 5. Make the next of prev_node as new_node */
    prev_Node.next = new_node;
 
    /* 6. Make prev_node as previous of new_node */
    new_node.prev = prev_Node;
 
    /* 7. Change previous of new_node"s next node */
    if (new_node.next != null)
        new_node.next.prev = new_node;
}
 
// This code is contributed by aashish1995

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

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

Шесть из 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. Установите предыдущий указатель следующего узла как 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. В противном случае, если предыдущее значение new_node равно NULL, это будет новый головной узел. Итак, make (* head_ref) = new_node.

Below is the implementation of the above approach: 

C++

// A complete working C program to demonstrate all
// insertion before a given node
#include <stdio.h>
#include <stdlib.h>
 
// A linked list node
struct Node {
    int data;
    struct Node* next;
    struct Node* prev;
};
 
/* Given a reference (pointer to pointer) to the head of a
list and an int, inserts a new node on the front of the
list. */
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;
}
 
/* Given a node as next_node, insert a new node before the
 * given node */
void insertBefore(struct Node** head_ref,
                  struct Node* next_node, int new_data)
{
    /*1. check if the given next_node is NULL */
    if (next_node == NULL) {
        printf("the given next node cannot be NULL");
        return;
    }
 
    /* 2. allocate new node */
    struct Node* new_node
        = (struct Node*)malloc(sizeof(struct Node));
 
    /* 3. put in the data */
    new_node->data = new_data;
 
    /* 4. Make prev of new node as prev of next_node */
    new_node->prev = next_node->prev;
 
    /* 5. Make the prev of next_node as new_node */
    next_node->prev = new_node;
 
    /* 6. Make next_node as next of new_node */
    new_node->next = next_node;
 
    /* 7. Change next of new_node"s previous node */
    if (new_node->prev != NULL)
        new_node->prev->next = new_node;
    /* 8. If the prev of new_node is NULL, it will be
       the new head node */
    else
        (*head_ref) = new_node;
}
 
// This function prints contents of linked list starting
// from the given node
void printList(struct Node* node)
{
    struct Node* last;
    printf(" Traversal in forward direction ");
    while (node != NULL) {
        printf(" %d ", node->data);
        last = node;
        node = node->next;
    }
 
    printf(" Traversal in reverse direction ");
    while (last != NULL) {
        printf(" %d ", last->data);
        last = last->prev;
    }
}
 
/* Driver program to test above functions*/
int main()
{
    /* Start with the empty list */
    struct Node* head = NULL;
    push(&head, 7);
 
    push(&head, 1);
 
    push(&head, 4);
 
    // Insert 8, before 1. So linked list becomes
    // 4->8->1->7->NULL
    insertBefore(&head, head->next, 8);
 
    printf("Created DLL is: ");
    printList(head);
 
    getchar();
    return 0;
}

Python3

# A complete working Python program to demonstrate all
# insertion before a given node
 
# A linked list node
class Node:
    def __init__(self, x):
        self.data = x
        self.p
Структуры данных

РЕКОМЕНДУЕМЫЕ СТАТЬИ

Различия между структурой данных массива и словаря
21 Января, 2023
TCS SDE Sheet: Вопросы и ответы для интервью
12 Января, 2023
Множественные сравнения в очереди приоритетов С++?
6 Января, 2023
Когда использовать Queue over ArrayList в Java?
6 Января, 2023
Введение в связанный список — учебные пособия по структуре данных и алгоритмам
12 Декабря, 2022
Лист Google SDE: вопросы и ответы на собеседовании
12 Декабря, 2022
Введение в массивы — учебные пособия по структуре данных и алгоритмам
12 Декабря, 2022
Как подготовиться к ICFP или Международной конференции по функциональному программированию?
12 Декабря, 2022