Учебное пособие по двусвязному списку

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

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

Ниже приведены операции с данной DLL:

Добавьте узел перед DLL: новый узел всегда добавляется перед заголовком данного связанного списка. И вновь добавленный узел становится новым главой DLL и поддерживает глобальную переменную для подсчета общего количества узлов в это время.
Обход двусвязного списка
Вставка узла: это можно сделать тремя способами:
- В начале: новый созданный узел вставляется перед головным узлом, а заголовок указывает на новый узел.
- В конце: новый созданный узел вставляется в конец списка и указывает на новый узел.
- В заданной позиции: переместите заданную DLL в эту позицию ( пусть узел будет X ), затем выполните следующие действия:
  1. Измените следующий указатель нового узла на следующий указатель узла X.
  2. Измените предыдущий указатель следующего узла узла X на новый узел.
  3. Измените следующий указатель узла X на новый узел.
  4. Измените предыдущий указатель нового узла на узел X.
Удаление узла: это можно сделать тремя способами:
- В начале: переместите голову к следующему узлу, чтобы удалить узел в начале и сделать предыдущий указатель текущей головы равным NULL.
- И последнее: переместите хвост к предыдущему узлу, чтобы удалить узел в конце и сделать следующий указатель хвостового узла равным NULL.
- В заданной позиции: пусть предыдущий узел узла в позиции pos будет узлом X, а следующий узел - узлом Y, затем выполните следующие действия:
  1. Измените следующий указатель узла X на узел Y.
  2. Измените предыдущий указатель узла Y на узел X.

Below is the implementation of all the operations:

// C program to implement all functions
// used in Doubly Linked List
  
#include <stdio.h>
#include <stdlib.h>
int i = 0;
  
// Node for Doubly Linked List
typedef struct node {
    int key;
    struct node* prev;
    struct node* next;
  
} node;
  
// Head, Tail, first & temp Node
node* head = NULL;
node* first = NULL;
node* temp = NULL;
node* tail = NULL;
  
// Function to add a node in the
// Doubly Linked List
void addnode(int k)
{
  
    // Allocating memory
    // to the Node ptr
    node* ptr
        = (node*)malloc(sizeof(node));
  
    // Assign Key to value k
    ptr->key = k;
  
    // Next and prev pointer to NULL
    ptr->next = NULL;
    ptr->prev = NULL;
  
    // If Linked List is empty
    if (head == NULL) {
        head = ptr;
        first = head;
        tail = head;
    }
  
    // Else insert at the end of the
    // Linked List
    else {
        temp = ptr;
        first->next = temp;
        temp->prev = first;
        first = temp;
        tail = temp;
    }
  
    // Increment for number of Nodes
    // in the Doubly Linked List
    i++;
}
  
// Function to traverse the Doubly
// Linked List
void traverse()
{
    // Nodes points towards head node
    node* ptr = head;
  
    // While pointer is not NULL,
    // traverse and print the node
    while (ptr != NULL) {
  
        // Print key of the node
        printf("%d ", ptr->key);
        ptr = ptr->next;
    }
  
    printf("
");
}
  
// Function to insert a node at the
// beginning of the linked list
void insertatbegin(int k)
{
  
    // Allocating memory
    // to the Node ptr
    node* ptr
        = (node*)malloc(sizeof(node));
  
    // Assign Key to value k
    ptr->key = k;
  
    // Next and prev pointer to NULL
    ptr->next = NULL;
    ptr->prev = NULL;
  
    // If head is NULL
    if (head == NULL) {
        first = ptr;
        first = head;
        tail = head;
    }
  
    // Else insert at beginning and
    // change the head to current node
    else {
        temp = ptr;
        temp->next = head;
        head->prev = temp;
        head = temp;
    }
    i++;
}
  
// Function to insert Node at end
void insertatend(int k)
{
  
    // Allocating memory
    // to the Node ptr
    node* ptr
        = (node*)malloc(sizeof(node));
  
    // Assign Key to value k
    ptr->key = k;
  
    // Next and prev pointer to NULL
    ptr->next = NULL;
    ptr->prev = NULL;
  
    // If head is NULL
    if (head == NULL) {
        first = ptr;
        first = head;
        tail = head;
    }
  
    // Else insert at the end
    else {
        temp = ptr;
        temp->prev = tail;
        tail->next = temp;
        tail = temp;
    }
    i++;
}
  
// Function to insert Node at any
// position pos
void insertatpos(int k, int pos)
{
  
    // For Invalid Position
    if (pos < 1 || pos > i + 1) {
        printf("Please enter a"
               " valid position
");
    }
  
    // If position is at the front,
    // then call insertatbegin()
    else if (pos == 1) {
        insertatbegin(k);
    }
  
    // Postion is at length of Linked
    // list + 1, then insert at the end
    else if (pos == i + 1) {
        insertatend(k);
    }
  
    // Else traverse till position pos
    // and insert the Node
    else {
        node* src = head;
  
        // Move head pointer to pos
        while (pos--) {
            src = src->next;
        }
  
        // Allocate memory to new Node
        node **da, **ba;
        node* ptr
            = (node*)malloc(
                sizeof(node));
        ptr->next = NULL;
        ptr->prev = NULL;
        ptr->key = k;
  
        // Change the previous and next
        // pointer of the nodes inserted
        // with previous and next node
        ba = &src;
        da = &(src->prev);
        ptr->next = (*ba);
        ptr->prev = (*da);
        (*da)->next = ptr;
        (*ba)->prev = ptr;
        i++;
    }
}
  
// Function to delete node at the
// beginning of the list
void delatbegin()
{
    // Move head to next and
    // decrease length by 1
    head = head->next;
    i--;
}
  
// Function to delete at the end
// of the list
void delatend()
{
    // Mode tail to the prev and
    // decrease length by 1
    tail = tail->prev;
    tail->next = NULL;
    i--;
}
  
// Function to delete the node at
// a given position pos
void delatpos(int pos)
{
  
    // If invalid position
    if (pos < 1 || pos > i + 1) {
        printf("Please enter a"
               " valid position
");
    }
  
    // If position is 1, then
    // call delatbegin()
    else if (pos == 1) {
        delatbegin();
    }
  
    // If position is at the end, then
    // call delatend()
    else if (pos == i) {
        delatend();
    }
  
    // Else traverse till pos, and
    // delete the node at pos
    else {
        // Src node to find which
        // node to be deleted
        node* src = head;
        pos--;
  
        // Traverse node till pos
        while (pos--) {
            src = src->next;
        }
  
        // previous and after node
        // of the src node
        node **pre, **aft;
        pre = &(src->prev);
        aft = &(src->next);
  
        // Change the next and prev
        // pointer of pre and aft node
        (*pre)->next = (*aft);
        (*aft)->prev = (*pre);
  
        // Decrease the length of the
        // Linked List
        i--;
    }
}
  
// Driver Code
int main()
{
    // Adding node to the linked List
    addnode(2);
    addnode(4);
    addnode(9);
    addnode(1);
    addnode(21);
    addnode(22);
  
    // To print the linked List
    printf("Linked List: ");
    traverse();
  
    printf("
");
  
    // To insert node at the beginning
    insertatbegin(1);
    printf("Linked List after"
           " inserting 1 "
           "at beginning: ");
    traverse();
  
    // To insert at the end
    insertatend(0);
    printf("Linked List after "
           "inserting 0 at end: ");
    traverse();
  
    // To insert Node with
    // value 44 after 3rd Node
    insertatpos(44, 3);
    printf("Linked List after "
           "inserting 44 "
           "after 3rd Node: ");
    traverse();
  
    printf("
");
  
    // To delete node at the beginning
    delatbegin();
    printf("Linked List after "
           "deleting node "
           "at beginning: ");
    traverse();
  
    // To delete at the end
    delatend();
    printf("Linked List after "
           "deleting node at end: ");
    traverse();
  
    // To delete Node at position 5
    printf("Linked List after "
           "deleting node "
           "at position 5: ");
    delatpos(5);
    traverse();
  
    return 0;
}

Output:

Linked List: 2 4 9 1 21 22
Linked List after inserting 1 at beginning: 1 2 4 9 1 21 22
Linked List after inserting 0 at end: 1 2 4 9 1 21 22 0
Linked List after inserting 44 after 3rd Node: 1 2 4 44 9 1 21 22 0
Linked List after deleting node at beginning: 2 4 44 9 1 21 22 0
Linked List after deleting node at end: 2 4 44 9 1 21 22
Linked List after deleting node at position 5: 2 4 44 9 21 22

Вниманию читателя! Не прекращайте учиться сейчас. Освойте все важные концепции DSA с помощью самостоятельного курса DSA по приемлемой для студентов цене и будьте готовы к работе в отрасли. Чтобы завершить подготовку от изучения языка к DS Algo и многому другому, см. Полный курс подготовки к собеседованию .

Если вы хотите посещать живые занятия с отраслевыми экспертами, пожалуйста, обращайтесь к Geeks Classes Live и Geeks Classes Live USA.

Язык программирования Алгоритмы

Учебное пособие по двусвязному списку

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