Doubly Linked List Data Structures & Algorithms

In our previous article you have seen Double-ended Linked List. Doubly linked list is another variation of Linked Lists and don’t confuse with double-ended list.

An important problem that doubly linked list solves is it provides a way to traverse backward in the list, whereas with the ordinary linked lists it is difficult to traverse backward along the list. This limitation is overcome by doubly linked list.

Each link in doubly linked list has two references to other links instead of one link. The first reference is to the next link and the second reference is to the previous link.

Supported Operations

  • insertFirst() – insert at front of the list
  • insertLast() – insert at end of the list
  • insertAfter() – insert data after the specified key
  • deleteFirst() – delete first link
  • deleteLast() – delete last link
  • deleteKey() – delete link based on the key provided

Doubly Linked List Example

A doubly linked list need not be double-ended linked list (keep a reference to the last element in the list) necessarily. But in our example below we will include reference to the last element also.

Output

Drawback of doubly linked list

Every time you insert or delete a link you must deal with four links instead of two since each link has extra reference.

Recommended Posts

References

Leave a Reply

avatar
  Subscribe  
Notify of