Double Linked List

   Doubly Linked List is a variation of Linked list in which navigation is possible in both ways, either forward and backward easily as compared to Single Linked List. Following are the important terms to understand the concept of doubly linked list.
LinkedList − A Linked List contains the connection link to the first link called First and to the last link called Last.

  • Link − Each link of a linked list can store a data called an element.
  • Next − Each link of a linked list contains a link to the next link called Next.
  • Prev − Each link of a linked list contains a link to the previous link called Prev.
Doubly Linked List

Basic Operations

Following are the basic operations supported by a list.
  • Insertion − Adds an element at the beginning of the list.
  • Deletion − Deletes an element at the beginning of the list.
  • Insert Last − Adds an element at the end of the list.
  • Delete Last − Deletes an element from the end of the list.
  • Insert After − Adds an element after an item of the list.
  • Delete − Deletes an element from the list using the key.
  • Display forward − Displays the complete list in a forward manner.
  • Display backward − Displays the complete list in a backward manner.

Advantages over singly linked list

1) A DLL can be traversed in both forward and backward direction.
2) The delete operation in DLL is more efficient if pointer to the node to be deleted is given.
3) We can quickly insert a new node before a given node.
In singly linked list, to delete a node, pointer to the previous node is needed. To get this previous node, sometimes the list is traversed. In DLL, we can get the previous node using previous pointer.

Disadvantages over singly linked list

1) Every node of DLL Require extra space for an previous pointer. It is possible to implement DLL with single pointer though.
2) All operations require an extra pointer previous to be maintained. For example, in insertion, we need to modify previous pointers together with next pointers. For example in following functions for insertions at different positions, we need 1 or 2 extra steps to set previous pointer.

Comments

Post a Comment

Popular posts from this blog

AVL Tree & B Tree

Image
AVL Tree AVL tree is a self-balancing binary search tree in which each node maintains an extra information called as balance factor whose value is either -1, 0 or +1. AVL tree got its name after its inventor Georgy Adelson-Velsky and Landis. Balance Factor Balance factor of a node in an AVL tree is the difference between the height of the left subtree and that of right subtree of that node. Balance Factor = (Height of Left Subtree - Height of Right Subtree) or (Height of Right Subtree - Height of Left Subtree) The self balancing property of an avl tree is maintained by the balance factor. The value of balance factor should always be -1, 0 or +1. AVL Rotations Left Rotation If a tree becomes unbalanced, when a node is inserted into the right subtree of the right subtree, then we perform a single left rotation Right Rotation AVL tree may become unbalanced, if a node is inserted in the left subtree of the left subtree. The tree then needs a right
Read more

Binary Tree

Image
A binary tree is made of nodes, where each node contains a "left" pointer, a "right" pointer, and a data element. The "root" pointer points to the topmost node in the tree. The left and right pointers recursively point to smaller "subtrees" on either side. A null pointer represents a binary tree with no elements -- the empty tree. The formal recursive definition is: a  binary tree  is either empty (represented by a null pointer), or is made of a single node, where the left and right pointers (recursive definition ahead) each point to a  binary tree .        A "binary search tree" (BST) or "ordered binary tree" is a type of binary tree where the nodes are arranged in order: for each node, all elements in its left subtree are less-or-equal to the node (<=), and all the elements in its right subtree are greater than the node (>).  Types of binary tree A  full binary tree  which is also called as
Read more

Data Structure Summary

Image
Linked List LinkedList  − A Linked List contains the connection link to the first link called First and to the last link called Last. Singly Linked List   A singly linked list is a set of nodes where each node has two fields ‘data’ and ‘link’. The ‘data’ field stores actual piece of information and ‘link’ field is used to point to next node. Doubly Linked List A doubly linked list  contains an extra pointer, typically called  previous pointer , together with next pointer and data which are there in singly linked list. Difference between Singly linked list and Doubly linked list In SingleLinkList, the traversal can be done using the next node link only. In DoublyLinkList, the traversal can be done using the previous node link or the next node link. The SingleLinkList occupies less memory than DoublyLinkList as it has only 2 fields. The DoublyLinkList occupies more memory than SingleLinkList as it has 3 fields. Less efficient access to elements. More efficient
Read more