雙向連結串列資料結構

什麼是雙向連結串列？

雙向連結串列是連結串列的一種變體，與單向連結串列相比，它可以輕鬆地雙向導航（向前和向後）。以下是一些理解雙向連結串列概念的重要術語。

• 連結 − 連結串列的每個連結都可以儲存稱為元素的資料。

• 下一個 − 連結串列的每個連結都包含一個指向下一個連結的連結，稱為“下一個”。

• 前一個 − 連結串列的每個連結都包含一個指向前一個連結的連結，稱為“前一個”。

• 連結串列 − 連結串列包含指向第一個連結（稱為“第一個”）和最後一個連結（稱為“最後一個”）的連線連結。

雙向連結串列表示

根據以上說明，以下是要考慮的重要事項。

• 雙向連結串列包含一個稱為“第一個”和“最後一個”的連結元素。

• 每個連結都包含一個或多個數據欄位和一個稱為“下一個”的連結欄位。

• 每個連結都使用其“下一個”連結與其下一個連結連結。

• 每個連結都使用其“前一個”連結與其前一個連結連結。

• 最後一個連結包含一個空連結，以標記列表的結尾。

雙向連結串列的基本操作

以下是列表支援的基本操作。

• 插入 − 在列表開頭新增一個元素。

• 插入末尾 − 在列表末尾新增一個元素。

• 插入到之後 − 在列表的一個專案之後新增一個元素。

• 刪除 − 刪除列表開頭的元素。

• 刪除末尾 − 刪除列表末尾的元素。

• 刪除 − 使用鍵從列表中刪除一個元素。

• 向前顯示 − 以向前的方式顯示整個列表。

• 向後顯示 − 以向後的方式顯示整個列表。

雙向連結串列 - 在開頭插入

在此操作中，我們建立一個具有三個部分的新節點，一個包含資料，其他兩個包含其在列表中前一個和下一個節點的地址。此新節點插入到列表的開頭。

演算法

1. START
2. Create a new node with three variables: prev, data, next.
3. Store the new data in the data variable
4. If the list is empty, make the new node as head.
5. Otherwise, link the address of the existing first node to the 
next variable of the new node, and assign null to the prev variable.
6. Point the head to the new node.
7. END

示例

以下是此操作在各種程式語言中的實現：

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <stdbool.h>
struct node {
   int data;
   int key;
   struct node *next;
   struct node *prev;
};

//this link always point to first Link
struct node *head = NULL;

//this link always point to last Link
struct node *last = NULL;
struct node *current = NULL;

//is list empty
bool isEmpty(){
   return head == NULL;
}

//display the doubly linked list
void printList(){
   struct node *ptr = head;
   while(ptr != NULL) {
      printf("(%d,%d) ",ptr->key,ptr->data);
      ptr = ptr->next;
   }
}

//insert link at the first location
void insertFirst(int key, int data){

   //create a link
   struct node *link = (struct node*) malloc(sizeof(struct node));
   link->key = key;
   link->data = data;
   if(isEmpty()) {

      //make it the last link
      last = link;
   } else {

      //update first prev link
      head->prev = link;
   }

   //point it to old first link
   link->next = head;

   //point first to new first link
   head = link;
}
void main(){
   insertFirst(1,10);
   insertFirst(2,20);
   insertFirst(3,30);
   insertFirst(4,1);
   insertFirst(5,40);
   insertFirst(6,56);
   printf("\nDoubly Linked List: ");
   printList();
}

Doubly Linked List: (6,56) (5,40) (4,1) (3,30) (2,20) (1,10) 

#include <iostream>
#include <cstring>
#include <cstdlib>
#include <cstdbool>
struct node {
   int data;
   int key;
   struct node *next;
   struct node *prev;
};

//this link always point to first Link
struct node *head = NULL;

//this link always point to last Link
struct node *last = NULL;
struct node *current = NULL;

//is list empty
bool isEmpty(){
   return head == NULL;
}

//display the doubly linked list
void printList(){
   struct node *ptr = head;
   while(ptr != NULL) {
      printf("(%d,%d) ",ptr->key,ptr->data);
      ptr = ptr->next;
   }
}

//insert link at the first location
void insertFirst(int key, int data){

   //create a link
   struct node *link = (struct node*) malloc(sizeof(struct node));
   link->key = key;
   link->data = data;
   if(isEmpty()) {

      //make it the last link
      last = link;
   } else {

      //update first prev link
      head->prev = link;
   }

   //point it to old first link
   link->next = head;

   //point first to new first link
   head = link;
}
int main(){
   insertFirst(1,10);
   insertFirst(2,20);
   insertFirst(3,30);
   insertFirst(4,1);
   insertFirst(5,40);
   insertFirst(6,56);
   printf("Doubly Linked List: ");
   printList();
   return 0;
}

Doubly Linked List: (6,56) (5,40) (4,1) (3,30) (2,20) (1,10) 

//Java code for doubly linked list
import java.util.*;
class Node {
    public int data;
    public int key;
    public Node next;
    public Node prev;
    public Node(int data, int key) {
        this.data = data;
        this.key = key;
        this.next = null;
        this.prev = null;
    }
}
public class Main {
    //this link always point to first Link
    static Node head = null;
    //this link always point to last Link
    static Node last = null;
    static Node current = null;
    // is list empty
    public static boolean is_empty() {
        return head == null;
    }
    //display the doubly linked list
    public static void print_list() {
        Node ptr = head;
        while (ptr != null) {
            System.out.println("(" + ptr.key + "," + ptr.data + ")");
            ptr = ptr.next;
        }
    }
    //insert link at the first location
    public static void insert_first(int key, int data) {
          //create a link
        Node link = new Node(data, key);
        if (is_empty()) {
            //make it the last link
            last = link;
        } else {
            //update first prev link
            head.prev = link;
        }
        //point it to old first link
        link.next = head;
         //point first to new first link
        head = link;
    }
    public static void main(String[] args) {
        insert_first(1, 10);
        insert_first(2, 20);
        insert_first(3, 30);
        insert_first(4, 1);
        insert_first(5, 40);
        insert_first(6, 56);
        System.out.println("Doubly Linked List: ");
        print_list();
    }
}

Doubly Linked List: (6,56)(5,40)(4,1)(3,30)(2,20)(1,10)

#Python code for doubly linked list
class Node:
    def __init__(self, data=None, key=None):
        self.data = data
        self.key = key
        self.next = None
        self.prev = None
#this link always point to first Link
head = None
#this link always point to last Link
last = None
current = None
#is list empty
def is_empty():
    return head == None
#display the doubly linked list
def print_list():
    ptr = head
    while ptr != None:
        print(f"({ptr.key},{ptr.data})")
        ptr = ptr.next
#insert link at the first location
def insert_first(key, data):
    global head, last
    #create a link
    link = Node(data, key)
    if is_empty():
        #make it the last link
        last = link
    else:
        #update first prev link
        head.prev = link
    #point it to old first link
    link.next = head
    #point first to new first link
    head = link
insert_first(1,10)
insert_first(2,20)
insert_first(3,30)
insert_first(4,1)
insert_first(5,40)
insert_first(6,56)
print("Doubly Linked List: ")
print_list()

Doubly Linked List: 
(6,56) (5,40) (4,1) (3,30) (2,20) (1,10)

雙向連結串列 - 在末尾插入

在此插入操作中，新的輸入節點將新增到雙向連結串列的末尾；如果列表非空。如果列表為空，則頭將指向新節點。

演算法

1. START
2. If the list is empty, add the node to the list and point 
   the head to it.
3. If the list is not empty, find the last node of the list.
4. Create a link between the last node in the list and the 
   new node.
5. The new node will point to NULL as it is the new last node.
6. END

示例

以下是此操作在各種程式語言中的實現：

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <stdbool.h>
struct node {
   int data;
   int key;
   struct node *next;
   struct node *prev;
};

//this link always point to first Link
struct node *head = NULL;

//this link always point to last Link
struct node *last = NULL;
struct node *current = NULL;

//is list empty
bool isEmpty(){
   return head == NULL;
}

//display the doubly linked list
void printList(){
   struct node *ptr = head;
   while(ptr != NULL) {
      printf("(%d,%d) ",ptr->key,ptr->data);
      ptr = ptr->next;
   }
}

//insert link at the first location
void insertFirst(int key, int data){

   //create a link
   struct node *link = (struct node*) malloc(sizeof(struct node));
   link->key = key;
   link->data = data;
   if(isEmpty()) {

      //make it the last link
      last = link;
   } else {

      //update first prev link
      head->prev = link;
   }

   //point it to old first link
   link->next = head;

   //point first to new first link
   head = link;
}

//insert link at the last location
void insertLast(int key, int data){
   
   //create a link
   struct node *link = (struct node*) malloc(sizeof(struct node));
   link->key = key;
   link->data = data;
   if(isEmpty()) {

      //make it the last link
      last = link;
   } else {

      //make link a new last link
      last->next = link;

      //mark old last node as prev of new link
      link->prev = last;
   }

   //point last to new last node
   last = link;
}
void main(){
   insertFirst(1,10);
   insertFirst(2,20);
   insertFirst(3,30);
   insertFirst(4,1);
   insertLast(5,40);
   insertLast(6,56);
   printf("Doubly Linked List: ");
   printList();
}

Doubly Linked List: (4,1) (3,30) (2,20) (1,10) (5,40) (6,56)

#include <iostream>
#include <cstring>
#include <cstdlib>
#include <cstdbool>
struct node {
   int data;
   int key;
   struct node *next;
   struct node *prev;
};

//this link always point to first Link
struct node *head = NULL;

//this link always point to last Link
struct node *last = NULL;
struct node *current = NULL;

//is list empty
bool isEmpty(){
   return head == NULL;
}

//display the doubly linked list
void printList(){
   struct node *ptr = head;
   while(ptr != NULL) {
      printf("(%d,%d) ",ptr->key,ptr->data);
      ptr = ptr->next;
   }
}

//insert link at the first location
void insertFirst(int key, int data){

   //create a link
   struct node *link = (struct node*) malloc(sizeof(struct node));
   link->key = key;
   link->data = data;
   if(isEmpty()) {

      //make it the last link
      last = link;
   } else {

      //update first prev link
      head->prev = link;
   }

   //point it to old first link
   link->next = head;

   //point first to new first link
   head = link;
}

//insert link at the last location
void insertLast(int key, int data){

   //create a link
   struct node *link = (struct node*) malloc(sizeof(struct node));
   link->key = key;
   link->data = data;
   if(isEmpty()) {

      //make it the last link
      last = link;
   } else {

      //make link a new last link
      last->next = link;

      //mark old last node as prev of new link
      link->prev = last;
   }

   //point last to new last node
   last = link;
}
int main(){
   insertFirst(1,10);
   insertFirst(2,20);
   insertFirst(3,30);
   insertFirst(4,1);
   insertLast(5,40);
   insertLast(6,56);
   printf("Doubly Linked List: ");
   printList();
   return 0;
}

Doubly Linked List: (4,1) (3,30) (2,20) (1,10) (5,40) (6,56) 

import java.util.*;
class Node {
    public int data;
    public int key;
    public Node next;
    public Node prev;
    public Node(int data, int key) {
        this.data = data;
        this.key = key;
        this.next = null;
        this.prev = null;
    }
}
public class Main {
    static Node head = null;
    static Node last = null;
    static Node current = null;
    public static boolean isEmpty() {
        return head == null;
    } 
    public static void printList() {
        Node ptr = head;
        while (ptr != null) {
            System.out.print("(" + ptr.key + "," + ptr.data + ") ");
            ptr = ptr.next;
        }
    }
    public static void insertFirst(int key, int data) {
        Node link = new Node(data, key);
        if (isEmpty()) {
            last = link;
        } else {
            head.prev = link;
        }
        link.next = head;
        head = link;
    }
    public static void insertLast(int key, int data) {
        Node link = new Node(data, key);
        if (isEmpty()) {
            last = link;
        } else {
            last.next = link;
            link.prev = last;
        }
        last = link;
    }
    
    public static void main(String[] args) {
        insertFirst(1,10);
        insertFirst(2,20);
        insertFirst(3,30);
        insertFirst(4,1);
        insertLast(5,40);
        insertLast(6,56);
        System.out.print("Doubly Linked List: ");
        printList();
    }
}

Doubly Linked List: (4,1) (3,30) (2,20) (1,10) (5,40) (6,56)

class Node:
    def __init__(self, data=None, key=None):
        self.data = data
        self.key = key
        self.next = None
        self.prev = None
head = None
last = None
current = None
def isEmpty():
    return head == None
def printList():
    ptr = head
    while ptr != None:
        print(f"({ptr.key},{ptr.data})", end=" ")
        ptr = ptr.next
def insertFirst(key, data):
    global head, last
    link = Node(data, key)
    if isEmpty():
        last = link
    else:
        head.prev = link
    link.next = head
    head = link
def insertLast(key, data):
    global head, last
    link = Node(data, key)
    if isEmpty():
        last = link
    else:
        last.next = link
        link.prev = last
    last = link
insertFirst(1,10)
insertFirst(2,20)
insertFirst(3,30)
insertFirst(4,1)
insertLast(5,40)
insertLast(6,56)
print("Doubly Linked List: ", end="")
printList()

Doubly Linked List: (4,1) (3,30) (2,20) (1,10) (5,40) (6,56)

雙向連結串列 - 在開頭刪除

此刪除操作刪除雙向連結串列中現有的第一個節點。頭將移至下一個節點，並刪除連結。

演算法

1. START
2. Check the status of the doubly linked list
3. If the list is empty, deletion is not possible
4. If the list is not empty, the head pointer is 
   shifted to the next node.
5. END

示例

以下是此操作在各種程式語言中的實現：

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <stdbool.h>
struct node {
   int data;
   int key;
   struct node *next;
   struct node *prev;
};

//this link always point to first Link
struct node *head = NULL;

//this link always point to last Link
struct node *last = NULL;
struct node *current = NULL;

//is list empty
bool isEmpty(){
   return head == NULL;
}

//display the doubly linked list
void printList(){
   struct node *ptr = head;
   while(ptr != NULL) {
      printf("(%d,%d) ",ptr->key,ptr->data);
      ptr = ptr->next;
   }
}

//insert link at the first location
void insertFirst(int key, int data){

   //create a link
   struct node *link = (struct node*) malloc(sizeof(struct node));
   link->key = key;
   link->data = data;
   if(isEmpty()) {

      //make it the last link
      last = link;
   } else {

      //update first prev link
      head->prev = link;
   }

   //point it to old first link
   link->next = head;

   //point first to new first link
   head = link;
}

//delete first item
struct node* deleteFirst(){

   //save reference to first link
   struct node *tempLink = head;

   //if only one link
   if(head->next == NULL) {
      last = NULL;
   } else {
      head->next->prev = NULL;
   }
   head = head->next;

   //return the deleted link
   return tempLink;
}
void main(){
   insertFirst(1,10);
   insertFirst(2,20);
   insertFirst(3,30);
   insertFirst(4,1);
   insertFirst(5,40);
   insertFirst(6,56);
   printf("Doubly Linked List: \n");
   printList();
   printf("\nList after deleting first record: \n");
   deleteFirst();
   printList();
}

Doubly Linked List: (6,56) (5,40) (4,1) (3,30) (2,20) (1,10) 
List after deleting first record: (5,40) (4,1) (3,30) (2,20) (1,10) 

#include <iostream>
#include <cstring>
#include <cstdlib>
#include <cstdbool>
struct node {
   int data;
   int key;
   struct node *next;
   struct node *prev;
};

//this link always point to first Link
struct node *head = NULL;

//this link always point to last Link
struct node *last = NULL;
struct node *current = NULL;

//is list empty
bool isEmpty(){
   return head == NULL;
}

//display the doubly linked list
void printList(){
   struct node *ptr = head;
   while(ptr != NULL) {
      printf("(%d,%d) ",ptr->key,ptr->data);
      ptr = ptr->next;
   }
}

//insert link at the first location
void insertFirst(int key, int data){

   //create a link
   struct node *link = (struct node*) malloc(sizeof(struct node));
   link->key = key;
   link->data = data;
   if(isEmpty()) {

      //make it the last link
      last = link;
   } else {

      //update first prev link
      head->prev = link;
   }

   //point it to old first link
   link->next = head;

   //point first to new first link
   head = link;
}

//delete first item
struct node* deleteFirst(){

   //save reference to first link
   struct node *tempLink = head;

   //if only one link
   if(head->next == NULL) {
      last = NULL;
   } else {
      head->next->prev = NULL;
   }
   head = head->next;

   //return the deleted link
   return tempLink;
}
int main(){
   insertFirst(1,10);
   insertFirst(2,20);
   insertFirst(3,30);
   insertFirst(4,1);
   insertFirst(5,40);
   insertFirst(6,56);
   printf("Doubly Linked List: \n");
   printList();
   printf("\nList after deleting first record: \n");
   deleteFirst();
   printList();
   return 0;
}

Doubly Linked List: 
(6,56) (5,40) (4,1) (3,30) (2,20) (1,10) 
List after deleting first record: 
(5,40) (4,1) (3,30) (2,20) (1,10) 

//Java code for doubly linked list
import java.util.*;
class Node {
    public int data;
    public int key;
    public Node next;
    public Node prev;
    public Node(int data, int key) {
        this.data = data;
        this.key = key;
        this.next = null;
        this.prev = null;
    }
}
public class Main {
    //this link always point to first Link
    public static Node head = null;
    //this link always point to last Link
    public static Node last = null;
    //this link always point to current Link
    public static Node current = null;
    //is list empty
    public static boolean isEmpty() {
        return head == null;
    }
    //display the doubly linked list
    public static void printList() {
        Node ptr = head;
        while (ptr != null) {
            System.out.print("(" + ptr.key + "," + ptr.data + ") ");
            ptr = ptr.next;
        }
    }
    //insert link at the first location
    public static void insertFirst(int key, int data) {
        //create a link
        Node link = new Node(data, key);
        if (isEmpty()) {
            //make it the last link
            last = link;
        } else {
            //update first prev link
            head.prev = link;
        }
        //point it to old first link
        link.next = head;
        head = link;
    }
    //delete the first item
    public static Node deleteFirst() {
        //save reference to first link
        Node tempLink = head;
        //if only one link
        if (head.next == null) {
            last = null;
        } else {
            head.next.prev = null;
        }
        head = head.next;
        //return the deleted link
        return tempLink;
    }
    public static void main(String[] args) {
        insertFirst(1, 10);
        insertFirst(2, 20);
        insertFirst(3, 30);
        insertFirst(4, 1);
        insertFirst(5, 40);
        insertFirst(6, 56);
        System.out.print("Doubly Linked List: \n");
        printList();
        System.out.print("\nList after deleting first record: \n");
        deleteFirst();
        printList();
    }
}

Doubly Linked List: 
(6,56) (5,40) (4,1) (3,30) (2,20) (1,10) 
List after deleting first record: 
(5,40) (4,1) (3,30) (2,20) (1,10) 

#Python code for doubly linked list
class Node:
    def __init__(self, data=None, key=None):
        self.data = data
        self.key = key
        self.next = None
        self.prev = None
#this link always point to first Link
head = None
#this link always point to last Link
last = None
current = None
#is list empty
def isEmpty():
    return head == None
#display the doubly linked list
def printList():
    ptr = head
    while ptr != None:
        print(f"({ptr.key},{ptr.data}) ", end="")
        ptr = ptr.next
#insert link at the first location
def insertFirst(key, data):
    #create a link
    global head, last
    link = Node(data, key)
    if isEmpty():
        #make it the last link
        last = link
    else:
        #update first prev link
        head.prev = link
    #point it to old first link
    link.next = head
    head = link
#delete first item
def deleteFirst():
     #save reference to first link
    global head, last
    tempLink = head
    #if only one link
    if head.next == None:
        last = None
    else:
        head.next.prev = None
    head = head.next
    #return the deleted link
    return tempLink
insertFirst(1,10)
insertFirst(2,20)
insertFirst(3,30)
insertFirst(4,1)
insertFirst(5,40)
insertFirst(6,56)
print("Doubly Linked List:")
printList()
print("\nList after deleting first record:")
deleteFirst()
printList()

Doubly Linked List: 
(6,56) (5,40) (4,1) (3,30) (2,20) (1,10) 
List after deleting first record: 
(5,40) (4,1) (3,30) (2,20) (1,10) 

雙向連結串列 - 完整實現

以下是雙向連結串列在各種程式語言中的完整實現：

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <stdbool.h>
struct node {
   int data;
   int key;
   struct node *next;
   struct node *prev;
};

//this link always point to first Link
struct node *head = NULL;

//this link always point to last Link
struct node *last = NULL;
struct node *current = NULL;

//is list empty
bool isEmpty(){
   return head == NULL;
}

//display the list in from first to last
void displayForward(){

   //start from the beginning
   struct node *ptr = head;

   //navigate till the end of the list
   printf("\n[ ");
   while(ptr != NULL) {
      printf("(%d,%d) ",ptr->key,ptr->data);
      ptr = ptr->next;
   }
   printf(" ]");
}

//display the list from last to first
void displayBackward(){

//start from the last
   struct node *ptr = last;

   //navigate till the start of the list
   printf("\n[ ");
   while(ptr != NULL) {

      //print data
      printf("(%d,%d) ",ptr->key,ptr->data);

      //move to next item
      ptr = ptr ->prev;
      printf(" ");
   }
   printf(" ]");
}

//insert link at the first location
void insertFirst(int key, int data){

   //create a link
   struct node *link = (struct node*) malloc(sizeof(struct node));
   link->key = key;
   link->data = data;
   if(isEmpty()) {

      //make it the last link
      last = link;
   } else {

      //update first prev link
      head->prev = link;
   }

   //point it to old first link
   link->next = head;

   //point first to new first link
   head = link;
}

//insert link at the last location
void insertLast(int key, int data){

   //create a link
   struct node *link = (struct node*) malloc(sizeof(struct node));
   link->key = key;
   link->data = data;
   if(isEmpty()) {

      //make it the last link
      last = link;
   } else {

      //make link a new last link
      last->next = link;

      //mark old last node as prev of new link
      link->prev = last;
   }

   //point last to new last node
   last = link;
}

//delete first item
struct node* deleteFirst(){

   //save reference to first link
   struct node *tempLink = head;

   //if only one link
   if(head->next == NULL) {
      last = NULL;
   } else {
      head->next->prev = NULL;
   }
   head = head->next;

   //return the deleted link
   return tempLink;
}

//delete link at the last location
struct node* deleteLast(){

   //save reference to last link
   struct node *tempLink = last;

   //if only one link
   if(head->next == NULL) {
      head = NULL;
   } else {
      last->prev->next = NULL;
   }
   last = last->prev;

   //return the deleted link
   return tempLink;
}

//delete a link with given key
struct node* delete(int key){

   //start from the first link
   struct node* current = head;
   struct node* previous = NULL;

   //if list is empty
   if(head == NULL) {
      return NULL;
   }

   //navigate through list
   while(current->key != key) {

      //if it is last node
      if(current->next == NULL) {
         return NULL;
      } else {

         //store reference to current link
         previous = current;

         //move to next link
         current = current->next;
      }
   }

   //found a match, update the link
   if(current == head) {

      //change first to point to next link
      head = head->next;
   } else {

      //bypass the current link
      current->prev->next = current->next;
   }
   if(current == last) {

      //change last to point to prev link
      last = current->prev;
   } else {
      current->next->prev = current->prev;
   }
   return current;
}
bool insertAfter(int key, int newKey, int data){

   //start from the first link
   struct node *current = head;

   //if list is empty
   if(head == NULL) {
      return false;
   }

   //navigate through list
   while(current->key != key) {

      //if it is last node
      if(current->next == NULL) {
         return false;
      } else {

         //move to next link
         current = current->next;
      }
   }

   //create a link
   struct node *newLink = (struct node*) malloc(sizeof(struct node));
   newLink->key = key;
   newLink->data = data;
   if(current == last) {
      newLink->next = NULL;
      last = newLink;
   } else {
      newLink->next = current->next;
      current->next->prev = newLink;
   }
   newLink->prev = current;
   current->next = newLink;
   return true;
}
int main(){
   insertFirst(1,10);
   insertFirst(2,20);
   insertFirst(3,30);
   insertFirst(4,1);
   insertFirst(5,40);
   insertFirst(6,56);
   printf("\nList (First to Last): ");
   displayForward();
   printf("\n");
   printf("\nList (Last to first): ");
   displayBackward();
   printf("\nList , after deleting first record: ");
   deleteFirst();
   displayForward();
   printf("\nList , after deleting last record: ");
   deleteLast();
   displayForward();
   printf("\nList , insert after key(4) : ");
   insertAfter(4,7, 13);
   displayForward();
   printf("\nList , after delete key(4) : ");
   delete(4);
   displayForward();
}

List (First to Last): 
[ (6,56) (5,40) (4,1) (3,30) (2,20) (1,10)  ]

List (Last to first): 
[ (1,10)  (2,20)  (3,30)  (4,1)  (5,40)  (6,56)   ]
List , after deleting first record: 
[ (5,40) (4,1) (3,30) (2,20) (1,10)  ]
List , after deleting last record: 
[ (5,40) (4,1) (3,30) (2,20)  ]
List , insert after key(4) : 
[ (5,40) (4,1) (4,13) (3,30) (2,20)  ]
List , after delete key(4) : 
[ (5,40) (4,13) (3,30) (2,20)  ]

#include <iostream>
#include <cstring>
#include <cstdlib>
#include <cstdbool>
using namespace std;
struct node {
   int data;
   int key;
   struct node *next;
   struct node *prev;
};

//this link always point to first Link
struct node *head = NULL;

//this link always point to last Link
struct node *last = NULL;
struct node *current = NULL;

//is list empty
bool isEmpty(){
   return head == NULL;
}
//display the list in from first to last
void displayForward(){

   //start from the beginning
   struct node *ptr = head;

   //navigate till the end of the list
   cout << "\n[ ";
   while(ptr != NULL) {
      cout << "(" << ptr->key << "," << ptr->data << ")";
      ptr = ptr->next;
   }
   cout << " ]" << endl;
}

//display the list from last to first
void displayBackward(){

   //start from the last
   struct node *ptr = last;

   //navigate till the start of the list
   cout << "\n[ ";
   while(ptr != NULL) {

      //print data
      cout << "(" << ptr->key << "," << ptr->data << ")";

      //move to next item
      ptr = ptr ->prev;
      cout << " ";
   }
   cout << " ]" << endl;
}

//insert link at the first location
void insertFirst(int key, int data){

   //create a link
   struct node *link = (struct node*) malloc(sizeof(struct node));
   link->key = key;
   link->data = data;
   if(isEmpty()) {

      //make it the last link
      last = link;
   } else {

      //update first prev link
      head->prev = link;
   }

   //point it to old first link
   link->next = head;

   //point first to new first link
   head = link;
}

//insert link at the last location
void insertLast(int key, int data){

   //create a link
   struct node *link = (struct node*) malloc(sizeof(struct node));
   link->key = key;
   link->data = data;
   if(isEmpty()) {

      //make it the last link
      last = link;
   } else {

      //make link a new last link
      last->next = link;

      //mark old last node as prev of new link
      link->prev = last;
   }

   //point last to new last node
   last = link;
}

//delete first item
struct node* deleteFirst(){

   //save reference to first link
   struct node *tempLink = head;

   //if only one link
   if(head->next == NULL) {
      last = NULL;
   } else {
      head->next->prev = NULL;
   }
   head = head->next;

   //return the deleted link
   return tempLink;
}

//delete link at the last location
struct node* deleteLast(){

   //save reference to last link
   struct node *tempLink = last;

   //if only one link
   if(head->next == NULL) {
      head = NULL;
   } else {
      last->prev->next = NULL;
   }
   last = last->prev;

   //return the deleted link
   return tempLink;
}

//delete a link with given key
struct node* deletenode(int key){

   //start from the first link
   struct node* current = head;
   struct node* previous = NULL;

   //if list is empty
   if(head == NULL) {
      return NULL;
   }

   //navigate through list
   while(current->key != key) {

      //if it is last node
      if(current->next == NULL) {
         return NULL;
      } else {

         //store reference to current link
         previous = current;

         //move to next link
         current = current->next;
      }
   }

   //found a match, update the link
   if(current == head) {

      //change first to point to next link
      head = head->next;
   } else {
      
      //bypass the current link
      current->prev->next = current->next;
   }
   if(current == last) {

      //change last to point to prev link
      last = current->prev;
   } else {
      current->next->prev = current->prev;
   }
   return current;
}
bool insertAfter(int key, int newKey, int data){

   //start from the first link
   struct node *current = head;

   //if list is empty
   if(head == NULL) {
      return false;
   }

   //navigate through list
   while(current->key != key) {

      //if it is last node
      if(current->next == NULL) {
         return false;
      } else {

         //move to next link
         current = current->next;
      }
   }

   //create a link
   struct node *newLink = (struct node*) malloc(sizeof(struct node));
   newLink->key = key;
   newLink->data = data;
   if(current == last) {
      newLink->next = NULL;
      last = newLink;
   } else {
      newLink->next = current->next;
      current->next->prev = newLink;
   }
   newLink->prev = current;
   current->next = newLink;
   return true;
}
int main(){
   insertFirst(1,10);
   insertFirst(2,20);
   insertFirst(3,30);
   insertFirst(4,1);
   insertFirst(5,40);
   insertFirst(6,56);
   printf("\nList (First to Last): ");
   displayForward();
   printf("\n");
   printf("\nList (Last to first): ");
   displayBackward();
   printf("\nList , after deleting first record: ");
   deleteFirst();
   displayForward();
   printf("\nList , after deleting last record: ");
   deleteLast();
   displayForward();
   printf("\nList , insert after key(4) : ");
   insertAfter(4, 7, 13);
   displayForward();
   printf("\nList , after delete key(4) : ");
   deletenode(4);
   displayForward();
   return 0;
}

List (First to Last):
[ (6, 56) (5, 40) (4, 1) (3, 30) (2, 20) (1, 10) ]

List (Last to First):
[ (1, 10) (2, 20) (3, 30) (4, 1) (5, 40) (6, 56) ]
List, after deleting first record:
[ (5, 40) (4, 1) (3, 30) (2, 20) (1, 10) ]
List, after deleting last record:
[ (5, 40) (4, 1) (3, 30) (2, 20) ]
List, insert after key(4):
[ (5, 40) (4, 1) (7, 13) (3, 30) (2, 20) ]
List, after delete key(4):
[ (5, 40) (7, 13) (3, 30) (2, 20) ]

class Node {
    int data;
    int key;
    Node next;
    Node prev;

    public Node(int key, int data) {
        this.key = key;
        this.data = data;
        this.next = null;
        this.prev = null;
    }
}

class DoublyLinkedList {
    Node head;
    Node last;

    boolean isEmpty() {
        return head == null;
    }

    void displayForward() {
        Node ptr = head;
        System.out.print("[ ");
        while (ptr != null) {
            System.out.print("(" + ptr.key + "," + ptr.data + ") ");
            ptr = ptr.next;
        }
        System.out.println("]");
    }

    void displayBackward() {
        Node ptr = last;
        System.out.print("[ ");
        while (ptr != null) {
            System.out.print("(" + ptr.key + "," + ptr.data + ") ");
            ptr = ptr.prev;
        }
        System.out.println("]");
    }

    void insertFirst(int key, int data) {
        Node link = new Node(key, data);
        if (isEmpty()) {
            last = link;
        } else {
            head.prev = link;
        }
        link.next = head;
        head = link;
    }

    void insertLast(int key, int data) {
        Node link = new Node(key, data);
        if (isEmpty()) {
            last = link;
        } else {
            last.next = link;
            link.prev = last;
        }
        last = link;
    }

    Node deleteFirst() {
        if (isEmpty()) {
            return null;
        }
        Node tempLink = head;
        if (head.next == null) {
            last = null;
        } else {
            head.next.prev = null;
        }
        head = head.next;
        return tempLink;
    }

    Node deleteLast() {
        if (isEmpty()) {
            return null;
        }
        Node tempLink = last;
        if (head.next == null) {
            head = null;
        } else {
            last.prev.next = null;
        }
        last = last.prev;
        return tempLink;
    }

    Node delete(int key) {
        Node current = head;
        Node previous = null;
        if (head == null) {
            return null;
        }
        while (current.key != key) {
            if (current.next == null) {
                return null;
            } else {
                previous = current;
                current = current.next;
            }
        }
        if (current == head) {
            head = head.next;
        } else {
            current.prev.next = current.next;
        }
        if (current == last) {
            last = current.prev;
        } else {
            current.next.prev = current.prev;
        }
        return current;
    }

    boolean insertAfter(int key, int newKey, int data) {
        Node current = head;
        if (head == null) {
            return false;
        }
        while (current.key != key) {
            if (current.next == null) {
                return false;
            } else {
                current = current.next;
            }
        }
        Node newLink = new Node(newKey, data);
        if (current == last) {
            newLink.next = null;
            last = newLink;
        } else {
            newLink.next = current.next;
            current.next.prev = newLink;
        }
        newLink.prev = current;
        current.next = newLink;
        return true;
    }
}

public class Main {
    public static void main(String[] args) {
        DoublyLinkedList dll = new DoublyLinkedList();
        dll.insertFirst(1, 10);
        dll.insertFirst(2, 20);
        dll.insertFirst(3, 30);
        dll.insertFirst(4, 1);
        dll.insertFirst(5, 40);
        dll.insertFirst(6, 56);
        System.out.println("List (First to Last):");
        dll.displayForward();
        System.out.println();
        System.out.println("List (Last to First):");
        dll.displayBackward();
        System.out.println("List, after deleting first record:");
        dll.deleteFirst();
        dll.displayForward();
        System.out.println("List, after deleting last record:");
        dll.deleteLast();
        dll.displayForward();
        System.out.println("List, insert after key(4):");
        dll.insertAfter(4, 7, 13);
        dll.displayForward();
        System.out.println("List, after delete key(4):");
        dll.delete(4);
        dll.displayForward();
    }
}

List (First to Last):
[ (6, 56) (5, 40) (4, 1) (3, 30) (2, 20) (1, 10) ]

List (Last to First):
[ (1, 10) (2, 20) (3, 30) (4, 1) (5, 40) (6, 56) ]
List, after deleting first record:
[ (5, 40) (4, 1) (3, 30) (2, 20) (1, 10) ]
List, after deleting last record:
[ (5, 40) (4, 1) (3, 30) (2, 20) ]
List, insert after key(4):
[ (5, 40) (4, 1) (7, 13) (3, 30) (2, 20) ]
List, after delete key(4):
[ (5, 40) (7, 13) (3, 30) (2, 20) ]

class Node:
    def __init__(self, key, data):
        self.key = key
        self.data = data
        self.next = None
        self.prev = None

class DoublyLinkedList:
    def __init__(self):
        self.head = None
        self.last = None

    def is_empty(self):
        return self.head is None

    def display_forward(self):
        ptr = self.head
        print("[", end=" ")
        while ptr:
            print("({}, {})".format(ptr.key, ptr.data), end=" ")
            ptr = ptr.next
        print("]")

    def display_backward(self):
        ptr = self.last
        print("[", end=" ")
        while ptr:
            print("({}, {})".format(ptr.key, ptr.data), end=" ")
            ptr = ptr.prev
        print("]")

    def insert_first(self, key, data):
        link = Node(key, data)
        if self.is_empty():
            self.last = link
        else:
            self.head.prev = link
        link.next = self.head
        self.head = link

    def insert_last(self, key, data):
        link = Node(key, data)
        if self.is_empty():
            self.last = link
        else:
            self.last.next = link
            link.prev = self.last
        self.last = link

    def delete_first(self):
        if self.is_empty():
            return None
        temp_link = self.head
        if self.head.next is None:
            self.last = None
        else:
            self.head.next.prev = None
        self.head = self.head.next
        return temp_link

    def delete_last(self):
        if self.is_empty():
            return None
        temp_link = self.last
        if self.head.next is None:
            self.head = None
        else:
            self.last.prev.next = None
        self.last = self.last.prev
        return temp_link

    def delete(self, key):
        current = self.head
        while current and current.key != key:
            current = current.next
        if current is None:
            return None
        if current == self.head:
            self.head = self.head.next
        else:
            current.prev.next = current.next
        if current == self.last:
            self.last = current.prev
        else:
            current.next.prev = current.prev
        return current

    def insert_after(self, key, new_key, data):
        current = self.head
        while current and current.key != key:
            current = current.next
        if current is None:
            return False
        new_link = Node(new_key, data)
        if current == self.last:
            new_link.next = None
            self.last = new_link
        else:
            new_link.next = current.next
            current.next.prev = new_link
        new_link.prev = current
        current.next = new_link
        return True

# Example usage
dll = DoublyLinkedList()
dll.insert_first(1, 10)
dll.insert_first(2, 20)
dll.insert_first(3, 30)
dll.insert_first(4, 1)
dll.insert_first(5, 40)
dll.insert_first(6, 56)
print("List (First to Last):")
dll.display_forward()
print()
print("List (Last to First):")
dll.display_backward()
print("List, after deleting first record:")
dll.delete_first()
dll.display_forward()
print("List, after deleting last record:")
dll.delete_last()
dll.display_forward()
print("List, insert after key(4):")
dll.insert_after(4, 7, 13)
dll.display_forward()
print("List, after delete key(4):")
dll.delete(4)
dll.display_forward()	

List (First to Last):
[ (6, 56) (5, 40) (4, 1) (3, 30) (2, 20) (1, 10) ]

List (Last to First):
[ (1, 10) (2, 20) (3, 30) (4, 1) (5, 40) (6, 56) ]
List, after deleting first record:
[ (5, 40) (4, 1) (3, 30) (2, 20) (1, 10) ]
List, after deleting last record:
[ (5, 40) (4, 1) (3, 30) (2, 20) ]
List, insert after key(4):
[ (5, 40) (4, 1) (7, 13) (3, 30) (2, 20) ]
List, after delete key(4):
[ (5, 40) (7, 13) (3, 30) (2, 20) ]