Doubly Linked ListHello Everyone, Show Today I will be talking about a data structure called Doubly Linked List. Before I start talking about the Doubly linked list, I highly recommend reading my blog on Singly Linked List (Click Here). It will give you an overview of the Singly Linked List data. What is Doubly Linked List? A Doubly Linked List (points to two directions) very identical to Singly Linked List except it contains an extra pointer that keeps track of the previous node. Doubly Linked List has two pointers on every node that keeps track of the previous node and next node, unlike Singly Linked List which only keeps track of the next node. Just like the Singly Linked List, the first node in the Doubly Linked List is also called the head and the last node is also called the tail. In Doubly Linked List each node stores three things, data (integer or string), a reference to the next node and a previous node.  So in the picture above we have a head node (A) pointing to the next node (B) and then also has a previous pointer but there’s nothing there that’s why it's NULL. If we go to the node ( B ), you can see it's pointing to the next node ( C ) as well as it’s pointing to the previous node ( A ). Now let’s implement the Doubly Linked List (JavaScript). We need two classes one called Node, Other DoublyLinkedList.
constructor(val) { this.val = val; this.next = null; this.prev = null; } }class DoublyLinkedList { constructor() { this.head = null; this.tail = null; this.length = 0; } } At the moment Doubly Linked List doesn't do anything right now. Let’s write a method called the push to add a node to the end of the Doubly Linked List. class DoublyLinkedList {constructor() { this.head = null; this.tail = null; this.length = 0; }push(val) { let newNode = new Node(val); if (this.head === null) { this.head = newNode; this.tail = newNode; } else { this.tail.next = newNode; newNode.prev = this.tail this.tail = newNode; } this.length++ return this; } } Let’s Implement method Pop to remove from the end class DoublyLinkedList {constructor() { this.head = null; this.tail = null; this.length = 0; }push(val) { let newNode = new Node(val); if (this.head === null) { this.head = newNode; this.tail = newNode; } else { this.tail.next = newNode; newNode.prev = this.tail this.tail = newNode; } this.length++ return this; }pop() { if (!this.head) return undefined; let currentTail = this.tail; if (this.length === 1) { this.head = null this.tail = null } else { this.tail = currentTail.prev; this.tail.next = null; currentTail.prev = null; } this.length--; return currentTail; } } Next method Shift to remove from the beginning of the Doubly Linked List class DoublyLinkedList {constructor() { this.head = null; this.tail = null; this.length = 0; }push(val) { let newNode = new Node(val); if (this.head === null) { this.head = newNode; this.tail = newNode; } else { this.tail.next = newNode; newNode.prev = this.tail this.tail = newNode; } this.length++ return this; }pop() { if (!this.head) return undefined; let currentTail = this.tail; if (this.length === 1) { this.head = null this.tail = null } else { this.tail = currentTail.prev; this.tail.next = null; currentTail.prev = null; } this.length--; return currentTail; }shift() { let oldHead = this.head; if (this.length === 0) return undefined; else if (this.length === 1) { this.head = null; this.tail = null; } else { this.head = oldHead.next; this.head.prev = null; oldHead.next = null; } this.length--; return oldHead; } } Finally, a method that adds in the front called unshift. class DoublyLinkedList {constructor() { this.head = null; this.tail = null; this.length = 0; }push(val) { let newNode = new Node(val); if (this.head === null) { this.head = newNode; this.tail = newNode; } else { this.tail.next = newNode; newNode.prev = this.tail this.tail = newNode; } this.length++ return this; }pop() { if (!this.head) return undefined; let currentTail = this.tail; if (this.length === 1) { this.head = null this.tail = null } else { this.tail = currentTail.prev; this.tail.next = null; currentTail.prev = null; } this.length--; return currentTail; }shift() { let oldHead = this.head; if (this.length === 0) return undefined; else if (this.length === 1) { this.head = null; this.tail = null; } else { this.head = oldHead.next; this.head.prev = null; oldHead.next = null; } this.length--; return oldHead; }unshift(val) { let newNode = new Node(val); if (this.length === 0) { this.head = newNode; this.tail = newNode; } else { this.head.prev = newNode; newNode.next = this.head; this.head = newNode; } this.length++ return this } }
There you have it. I hope you found this blog helpful. If you're having any difficulty or need more explanation, I’m more than happy to help you. Please connect with me on LinkedIn or my email is . Happy Coding :) References: Doubly Linked List | Set 1 (Introduction and Insertion)We strongly recommend to refer following post as a prerequisite of this post. Following is representation of a DLL node in C language. C++
C
Java
Python3
C#
Javascript
Following are advantages/disadvantages of doubly linked list over singly linked list. Disadvantages over singly linked list Recommended: Please solve it on “PRACTICE” first, before moving on to the solution. 1) Add a node at the front: (A 5 steps process) Following are the 5 steps to add node at the front. C++
C
Java
Python3
C#
Javascript
Four steps of the above five steps are same as the 4 steps used for inserting at the front in singly linked list. The only extra step is to change previous of head. C++
C
Java
Python3
C#
Javascript
Five of the above steps step process are same as the 5 steps used for inserting after a given node in singly linked list. The two extra steps are needed to change previous pointer of new node and previous pointer of new node’s next node. Following are the 7 steps to add node at the end. C++
C
Java
Python3
C#
Javascript
Six of the above 7 steps are same as the 6 steps used for inserting after a given node in singly linked list. The one extra step is needed to change previous pointer of new node. Steps
Below is the implementation of the above approach: Code block Output: Created DLL is: Traversal in forward Direction 9 1 5 7 6 Traversal in reverse direction 6 7 5 1 9 A complete working program to test above functions. C++
C
Java
Python3
C#
Javascript
Output: Created DLL is: Traversal in forward Direction 1 7 5 8 6 4 Traversal in reverse direction 4 6 8 5 7 1Also see: Delete a node in double Link List
Article Tags :
Data Structures Linked List
doubly linked list Visa Practice Tags :
Visa Data Structures Linked List 5.6.1. Doubly Linked ListsThe singly linked list allows for direct access from a list node only to the next node in the list. A doubly linked list allows convenient access from a list node to the next node and also to the preceding node on the list. The doubly linked list node accomplishes this in the obvious way by storing two pointers: one to the node following it (as in the singly linked list), and a second pointer to the node preceding it. Figure 5.6.1: A doubly linked list. The most common reason to use a doubly linked list is because it is easier to implement than a singly linked list. While the code for the doubly linked implementation is a little longer than for the singly linked version, it tends to be a bit more “obvious” in its intention, and so easier to implement and debug. Whether a list implementation is doubly or singly linked should be hidden from the List class user. Like our singly linked list implementation, the doubly linked list implementation makes use of a header node. We also add a tailer node to the end of the list. The tailer is similar to the header, in that it is a node that contains no value, and it always exists. When the doubly linked list is initialized, the header and tailer nodes are created. Data member head points to the header node, and tail points to the tailer node. The purpose of these nodes is to simplify the insert, append, and remove methods by eliminating all need for special-case code when the list is empty, or when we insert at the head or tail of the list. In our implementation, curr will point to the current position (or to the trailer node if the current position is at the end of the list). Here is the complete implementation for a Link class to be used with doubly linked lists. This code is a little longer than that for the singly linked list node implementation since the doubly linked list nodes have an extra data member. class Link { // Doubly linked list node
private Object e; // Value for this node
private Link n; // Pointer to next node in list
private Link p; // Pointer to previous node
// Constructors
Link(Object it, Link inp, Link inn) { e = it; p = inp; n = inn; }
Link(Link inp, Link inn) { p = inp; n = inn; }
// Get and set methods for the data members
public Object element() { return e; } // Return the value
public Object setElement(Object it) { return e = it; } // Set element value
public Link next() { return n; } // Return next link
public Link setNext(Link nextval) { return n = nextval; } // Set next link
public Link prev() { return p; } // Return prev link
public Link setPrev(Link prevval) { return p = prevval; } // Set prev link
}
class Link { // Doubly linked list node
private E e; // Value for this node
private Link n; // Pointer to next node in list
private Link p; // Pointer to previous node
// Constructors
Link(E it, Link inp, Link inn) { e = it; p = inp; n = inn; }
Link(Link inp, Link inn) { p = inp; n = inn; }
// Get and set methods for the data members
public E element() { return e; } // Return the value
public E setElement(E it) { return e = it; } // Set element value
public Link next() { return n; } // Return next link
public Link setNext(Link nextval) { return n = nextval; } // Set next link
public Link prev() { return p; } // Return prev link
public Link setPrev(Link prevval) { return p = prevval; } // Set prev link
}
5.6.1.1. InsertThe following slideshows illustrate the insert and append doubly linked list methods. The class declaration and the remaining member functions for the doubly linked list class are nearly identical to the singly linked list version. While the code for these methods might be a little longer than their singly linked list counterparts (since there is an extra pointer in each node to deal with), they tend to be easier to understand. 5.6.1.4. PrevThe only disadvantage of the doubly linked list as compared to the singly linked list is the additional space used. The doubly linked list requires two pointers per node, and so in the implementation presented it requires twice as much overhead as the singly linked list. 5.6.1.5. Mangling PointersThere is a space-saving technique that can be employed to eliminate the additional space requirement, though it will complicate the implementation and be somewhat slower. Thus, this is an example of a space/time tradeoff. It is based on observing that, if we store the sum of two values, then we can get either value back by subtracting the other. That is, if we store \(a + b\) in variable \(c\), then \(b = c - a\) and \(a = c - b\). Of course, to recover one of the values out of the stored summation, the other value must be supplied. A pointer to the first node in the list, along with the value of one of its two link fields, will allow access to all of the remaining nodes of the list in order. This is because the pointer to the node must be the same as the value of the following node’s prev pointer, as well as the previous node’s next pointer. It is possible to move down the list breaking apart the summed link fields as though you were opening a zipper. The principle behind this technique is worth remembering, as it has many applications. The following code fragment will swap the contents of two variables without using a temporary variable (at the cost of three arithmetic operations). a = a + b;
b = a - b; // Now b contains original value of a
a = a - b; // Now a contains original value of b
a = a + b;
b = a - b; // Now b contains original value of a
a = a - b; // Now a contains original value of b
A similar effect can be had by using the exclusive-or operator. This fact is widely used in computer graphics. A region of the computer screen can be highlighted by XORing the outline of a box around it. XORing the box outline a second time restores the original contents of the screen. Doubly Linked List: A Complete Implementation GuideLesson 5 of 54By Simplilearn Last updated on Sep 19, 20213097PreviousNext
Table of ContentsView MoreA Doubly linked list is used in navigation systems or to represent a classic deck of cards. A Doubly linked list is a bidirectional linked list; i.e., you can traverse it from head to tail node or tail to head node. Unlike singly-linked lists, its node has an extra pointer that points at the last node. How Do You Implement a Doubly Linked List?You create nodes of doubly-linked lists using classes or structures. These nodes are then linked with each other using the next and the previous pointer. Code: //A c++ program to implement linked list #include <bits/stdc++.h> using namespace std; /* A class to create node */ class Node { public: int data; Node *next; Node *prev; }; //A function to insert at the //beginning of the list void push(Node** head, int newdata) { //create new node Node* newnode = new Node(); /* put in the data */ newnode->data = newdata; /* As we are adding at the beginning, prev is always NULL */ newnode->prev = NULL; /* link new node's next to head */ newnode->next = (*head); /* change prev of head node to newnode */ if((*head) != NULL) (*head)->prev = newnode ; /* changing head node */ (*head) = newnode; } /* A c++ program to print the list */ void printlist(Node *head) { while(head != NULL) { cout << head->data << " "; head = head->next; } } int main() { /* We will start with an empty list */ Node* head = NULL; /*lets create a linked list: 2->3->5->7 */ push(&head, 7); push(&head, 5); push(&head, 3); push(&head, 2); cout << "Created Doubly Linked list:" << endl; printlist(head); return 0; } Doubly Linked Lists - InsertionInsertion in doubly linked lists is similar to what we saw in the singly linked list with two exceptions:
|
Do doubly linked lists need a head?
Pos Terkait
Copyright © 2024 idkuu.com Inc.
