top of page

Doubly Linked List

Continue of Single Linked List . . . 

The two node links allow traversal of the list in either direction. While adding or removing a node in a doubly-linked list requires changing more links than the same operations on a singly linked list, the operations are simpler and potentially more efficient (for nodes other than first nodes) because there is no need to keep track of the previous node during traversal or no need to traverse the list to find the previous node, so that its link can be modified.

DSome operation in Doubly Linked list. most of the operations same as single Linked list..

 

Insert funtion

 

                 LIST-INSERT( L , x )

            1             x.next =  L.next

            2            If ( L.head != Null )

            3                    L.head.prev = x

            4            L.head = x

            5            x.prev = null

 

Search Funtion

 

             LIST-SEARCH (L ,  k )

            1           x = L.head

            2           while x != NIL and x.key != k

            3                     x = x.next

            4           return x

 

Delete funtion

 

            LIST-DELETE (L , x )

           1        if x.pre != NIL

           2                 x.pre.next =  x.next

           3        else   L.head = x.next

           4        if  x.next != NIL

           5        x.next.pre = x.pre

 Doubly Linked List implementation in C

 

1. /* Doubly Linked List implementation */
2. #include<stdio.h>
3. #include<stdlib.h>

4. struct Node {
5. ........int data;
6. ........struct Node* next;
7. ........struct Node* prev;
8. };

9. struct Node* head; // global variable - pointer to head node.
10. int length; // global variable - length of list

11. void init_list(){
12. ........head = nullptr;
13. ........length = 0;
14. }

15. bool is_list_empty(){
16. ........if (length == 0){
17. ..................return true;
18. ........}
19. ........return false;
20. }

21. struct Node* search(int element){


22. ........struct Node* newNode = head;
23. ........while (newNode != nullptr)
24. ........{
25. ................if (newNode->data == element){
26. .........................return newNode;
27. ................}
28. ................newNode = newNode->next;
29. .......}
30. }

31. bool deleteNode( int element){
32. ........struct Node* delNode = search(element);
33. ........if (delNode != NULL){
34. ................delNode->prev->next = delNode->next;
35. ................delete delNode;
36. ................return true;
37. ........}
38. ........else{
39. ................printf(" element not found! \n");
40. ................return false;
41. .......}
42. }
43. bool deleteat( int i){
44. ........if (i < length){
45. ................struct Node* newNode = head;
46. ................for (int j = 0; j < i; j++){
47. ......................newNode = newNode->next;
48. ................}
49. ................newNode->prev->next = newNode->next;
50. ................delete newNode;
51. ................return true;
52. .......}
53. ........printf(" List index not valid!.");
54. }

55. //Inserts a Node at tail of Doubly linked list
56. int insert(int element){
57. ........struct Node* temp = head;
58. ........struct Node* newNode
59. ................= (struct Node*)malloc(sizeof(struct Node));
60. ........newNode->data = element;
61. ........if (head == NULL) {
62. ................head = newNode;
63. ................return 1;
64. ........}
65. ........while (temp->next != NULL) temp = temp->next; // Go To last Node
66. ........temp->next = newNode;
67. ........newNode->prev = temp;
68. }

69. int insertat(int element, int i){
70. ........if (i < length){
71. ................struct Node* temp = head;
72. ................struct Node* newNode
73. ...........................= (struct Node*)malloc(sizeof(struct Node));
74. ................newNode->data = element;
75. ................if (head == NULL) {
76. ........................head = newNode;
77. ........................return 1;
78. ................}
79. ................int j = 0; // go to given index
80. ................while (j < i) { 
81. ................temp = temp->next;
82. .............................j++;
83. ................}
84. ................// insert after given index
85. ................newNode->next = temp->next;
86. ................temp->next = newNode;
87. ................newNode->prev = temp;
88. .......}
89. }

90. int list_length(){
91. .........return length;
92. }


93. //Prints all the elements in linked list in forward traversal order
94. void Print() {
95. ........struct Node* temp = head;
96. ........printf("Forward: ");
97. ........while (temp != NULL) {
98. ................printf("%d ", temp->data);
99. ................temp = temp->next;
100. ........}
101. ........printf("\n");
102. }

103. //Prints all elements in linked list in reverse traversal order. 
104. void ReversePrint() {
105. ........struct Node* temp = head;
106. ........if (temp == NULL) return; // empty list, exit
107. ........// Going to last Node
108. ........while (temp->next != NULL) {
109. ..............temp = temp->next;
110. ........}
111. .........// Traversing backward using prev pointer
112. ........printf("Reverse: ");
113. ........while (temp != NULL) {
114. ................printf("%d ", temp->data);
115. ................temp = temp->prev;
116. ........}
117. ........printf("\n");
118. }

119. int main() {
120. ......../*Driver code to test the implementation*/
121. ........head = NULL; // empty list. set head as NULL. 
122. ........// Calling an Insert and printing list both in forward as well as reverse direction. 
123. ........insert(2); Print(); ReversePrint();
124. ........insert(4); Print(); ReversePrint();
125. ........insert(6); Print(); ReversePrint();
126. ........insertat(8,2); Print(); ReversePrint();
127. ........system("PAUSE");
128. }

    Doubly Linked List – C++ Program source code

 

  1. #include <iostream>

  2.  

  3. using namespace std;

  4. typedef int E;

  5.  

  6. class Node {

  7. private:

  8.         E value;

  9.         Node* next;

  10.        Node* prev;

  11. public:

  12.         E Node::getValue();

  13.         void Node::setValue(E val);

  14.         Node* Node::getNext();

  15.         void Node::setNext(Node* newNode);

  16.         Node* Node::getprev();

  17.         void Node::setprev(Node* newNode);

  18. };

  19. class LinkedList {

  20.  

  21. private:

  22.          Node* head;

  23.          int length;

  24.  

  25. public:

  26.         void LinkedList::init_list();

  27.         bool LinkedList::is_list_empty();

  28.         bool LinkedList::search(E value);

  29.         E LinkedList::deleteNode(E value);

  30.         E LinkedList::deleteat(int i);

  31.         bool LinkedList::insert(E value);

  32.         bool LinkedList::insertat(E value, int i);

  33.         int LinkedList::list_length();

  34. };

  35.  

  36. using namespace std;

  37.  

  38. E Node::getValue(){

  39.         return this->value;

  40. }

  41. void Node::setValue(E val){

  42.        this->value = val;

  43. }

  44. Node* Node::getNext(){

  45.        return this->next;

  46. }

  47. void Node::setNext(Node* newNode){

  48.        this->next = newNode;

  49. }

  50. Node* Node::getprev(){

  51.        return this->prev;

  52. }

  53. void Node::setprev(Node* newNode){

  54.        this->prev = newNode;

  55. }

  56.                                                          

  57. using std::cout;

  58. using std::endl;

  59. // declaring the linked list

  60. void LinkedList::init_list(){

  61.          head = NULL;

  62.          length = 1;

  63. }

  64.  

  65. //cheak whether linked list is empty

  66. bool LinkedList::is_list_empty(){

  67.         if (head == NULL){

  68.                 return true;

  69.         }

  70.         return false;

  71. }

  72.  

  73. // searching value in the linked list

  74. bool LinkedList::search(E value){

  75.          Node* p = head;

  76. // declaring the pointer to travel thought linked list

  77.          if (is_list_empty()) // cheaking list is emply

  78.          {

  79.                 cout << "List is empty" << endl;

  80.                 return false;

  81.         }

  82.         while (p != NULL)

  83.         {        //conditional statement

  84.           if (p->getValue() == value){

  85.               cout << "The value is in the list" << endl;

  86.                         return true;

  87.                 }

  88.                 p = p->getNext();

  89.         }

  90.         cout << "value not in the list" << endl;

  91.  

  92. }

  93.  

  94. // deleting value in given location

  95. E LinkedList::deleteat(int i){

  96.          Node* p = head;

  97.          int l = list_length();

  98.          if (l < i){

  99.                 cout << "location not exist" << endl;

  100.                 return 0;

  101.         }

  102.         while (l>i - 1){

  103.                 p = p->getNext();

  104.         }

  105.         Node* del = p->getNext();

  106.         p->setNext(del->getNext());

  107.         cout << i << " th item deleted" << endl;

  108.         return 1;

  109. }

  110.  

  111. //insert the value to list at tail

  112. bool LinkedList::insert(E value){

  113.         Node* temp = head;

  114.         Node* newNode = new Node;

  115.         newNode->setvalue(value);

  116.         if( head == NULL){

  117.                 head = newNode;

  118.                 return 1;

  119.         }

  120.         while(temp->getNext() != NULL){

  121.                 temp = temp->getNext; // Go to last node

  122.         }

  123.         temp->setNext(newNode);

  124.         newNode->setprev(temp);

  125. }

  126.  

  127.  

  128. //insert the value to the given location

  129. bool LinkedList::insertat(E value, int i){

  130.         Node* p = head;

  131.         if (list_length() < i){

  132.                 cout << "location not exist" << endl;

  133.                 return false;

  134.         }

  135.         int l = list_length();

  136.         // travel to the given location

  137.         while (l>i){

  138.                p = p->getNext();

  139.         }

  140.         // craeting new node to set values

  141.         Node* N_node = new Node;

  142.         N_node->setValue(value);// setting value

  143.         N_node->setNext(p->getNext());// setting next pointer

  144.         p->setNext(N_node); // setting previous pointer

  145.         N_node->setprev(p);

  146.         length++; // increament the lenght of list

  147.         return true;

  148.  

  149. }

  150.  

  151. //return the length of the linked list

  152. int LinkedList::list_length(){

  153.         return length;

  154. }

  155.  

  156. void main(int argc, char **argv)

  157. {

  158.         /* Create an empty list */

  159.         LinkedList list1;

  160.         list1 init_list();

  161.         cout << "Created an empty list named list1 " << endl;

  162.         // inserting elements to the list

  163.         if (list1 insert(10)){

  164.                 cout << "Insert : 10" << endl;

  165.         }

  166.         if (list1 insert(24)){

  167.                  cout << "Insert : 24" << endl;

  168.         }

  169.         if (list1 insert(65)){

  170.                  cout << "Insert : 65" << endl;

  171.         }

  172.         cout << "search 35 in the list" << endl;

  173.         list1 search(35);

  174.         cout << "length of list :" << list1 list_length() << endl;

  175.         cout << "delete 2nd element" << endl;

  176.         list1 deleteat(2);

  177. }

 

 

Doubly Linked List Implementation in Java

 

  1. package    doubly_Lined_List;

  2. /**

  3. *

    1. @author    cse    helper

  4. */

  5. public class Node    {   

  6.                 private Node next;

  7.                 private Node back;

  8.                 private int value;

  9.  

  10.                 public void setValue ( int value ) {

  11.                                 this.value =  value;

  12.                 }

  13.                 public void setnext ( Node node ) {

  14.                                 next = node;

  15.                 }

  16.                 public void setback ( Node node ) {

  17.                                 back = node;

  18.                 }

  19.                 public int getValue ( ) {

  20.                                 return value;

  21.                 }

  22.                 public Node getnext(){

  23.                                 return next;

  24.                 }

  25.                 public Node getback(){

  26.                                 return back;

  27.                 }               

  28. }

  29.  

  30. public class Doubly_Linked_List    {       

  31.                     private Node head;

  32.                     private int length;

  33.  

  34.                 public void init_list ( ) {

  35.                                 head = null;

  36.                                 length = 0;

  37.                 }

  38.                 public boolean is_empty_list(){

  39.                                 if ( head == null ) {

  40.                                                 return true;

  41.                                 }

  42.                                 return false;

  43.                 }

  44.                 public boolean search (int value ) {

  45.                                 Node p = head;   

  46.                                 if ( is_empty_list ( ) ) {

  47.                                                 System.out.println("List    is    empty");

  48.                                                 return  false;

  49.                                 }

  50.                                 while(p != null){

  51.                                 if ( p.getValue ( ) ==  value ) {

  52.                                                     System.out.println("The value is in the list");

  53.                                                                 return true;

  54.                                 }   

  55.                                 p = p.getnext ( ) ;               

  56.                                 }

  57.                                 System.out.println("value not in the list");

  58.                                  return false;

  59.                 }

  60.                 public boolean insert ( int value){

  61.                                 Node  temp  = head;

  62.                                 Node  newNode =  new Node( ) ;

  63.                                 newNode.setValue ( value ) ;

  64.                                 if ( head == null ) {

  65.                                                 head =  newNode;

  66.                                                 length++;

  67.                                                 return true;

  68.                                 }else{

  69.                                                 while ( temp.getnext ( ) != null ) {

  70.                                                                 temp = temp.getnext ( ) ;

  71.                                                 }

  72.                                                 temp.setnext ( newNode ) ;

  73.                                                 newNode.setback ( temp ) ;

  74.                                                 length ++;

  75.                                                 return true;

  76.                                 }       

  77.                 }

  78.                 public boolean inserAt ( int  value ,int i ) {

  79.                                 Node p =  head;

  80.                                 if ( list_length ( ) < i ) {

  81.                                                 System.out.println ( " location    not    exist");

  82.                                                 return false;

  83.                                 }

  84.                                 int l = list_length ( ) ;

  85.                                 //travel to  given location

  86.                                 while ( l > i - 1 ) {

  87.                                                 p = p.getnext ( ) ;

  88.                                 }//creating new node to set values

  89.                                 Node newNode = new Node ( ) ;

  90.                                 newNode.setValue ( value ) ;    //    setting value

  91.                                 newNode.setnext( p.getnext ( ) ) ;

  92.                                 p.setnext ( newNode ) ;    //    setting previous node

  93.                                 newNode.setback ( p )  ;

  94.                                 length++;

  95.                                 return true;

  96.                 }

  97.                 public boolean delete( int value ) {

  98.                                 Node p = head;   

  99.                                 if ( is_empty_list ( ) ) {

  100.                                                 System.out.println ( "List is empty " ) ;

  101.                                                 return false;

  102.                                 }

  103.                                 //    if value in head deleted

  104.                                 if ( head.getValue ( ) == value ) {

  105.                                                 head = head.getnext ( ) ;

  106.                                                 head.setback ( null ) ;

  107.                                                 length- -;

  108.                                                 return true;

  109.                                 }

  110.                                 //    delete other node

  111.                                 while ( p !=  null) {

  112.                                                 if ( p.getValue ( ) == value ){

  113.                                                                 p.getback( ).setnext ( p.getnext ( ) ) ;

  114.                                                                 p.getnext( ).setback ( p.getback ( ) );

  115.                                                             System.out.println("The value is deleted");

  116.                                                                 length- - ;

  117.                                                                 return true;

  118.                                                 }    p = p.getnext();

  119.                                 }

  120.                                 System.out.println ( "value not in the list");

  121.                                 return false;   

  122.                 }

  123.                 public boolean deleteAt ( int i ) {

  124.                                 Node p =  head;

  125.                                 int l = list_length ( ) ;

  126.                                 if ( l < i ) {

  127.                                               System.out.println ( "Location not found ");

  128.                                                 return false;

  129.                                 }

  130.                                 while ( l  >  ( i - 1 ) ) {

  131.                                                 p = p.getnext ( ) ;

  132.                                 }

  133.                                 Node del = p.getnext ( ) ;

  134.                                 p.setnext ( del.getnext ( ) ) ;

  135.                 System.out.println ( String valueOf ( i ) +" th  item deleted    ");

  136.                                 length --;

  137.                                 return true;

  138.                 }

  139.                 public int list_length(){

  140.                                 return length;

  141.                 }

  142.                 public void printList(){

  143.                                 Node print =  head;

  144.                                 while(print  != null){

  145.                                                 System.out.print(print    getValue());

  146.                                                 System.out.print("    ");

  147.                                                 print  =  print. getnxt( );

  148.                                 }

  149.                                 System.out.println("");               

  150.                 }

  151.  

  152.                 public static void main( String[ ]    args){

  153.                             Doubly_Linked_List  list1  =  new Doubly_Linked_List();

  154.                                 list.init_list();

  155.                                 list1.insert(10);

  156.                                 list1.insert(20);

  157.                                 list1.printList();

  158.                                 list1. insert(15);

  159.                                 list1.printList();

  160.                                 list1.inserAt(45,  1);

  161.                                 list1.insert(36);

  162.                                 list1.delete(20);

  163.                                 list1.delete(6);

  164.                                 list1. search(14);

  165.                                 list1    deleteAt(2);

  166.                     }

  167. }

 

bottom of page