Doubly Linked Lists

A doubly linked list is a linked linear data structure,each node of which has one or more data fields but only two link fields known as left link (LLINK) and right link (RLINK).The LLINK field of a given node points to the node on its left and RLINK field of a given node points to the node on its right.

Advantages-

1.The availability of two links LLINK and RLINK permit forward and backward movement during the processing of the list.
2.The deletion of a node X from the list requires only the value of X.
3.Efficiency of operations like insertion,deletion,etc increases.

Disadvantage-

1.Each node needs two links which can be considered expensive storage-wise when compared to singly linked lists.

Operations-

Insertion-

To insert node X to the right of node Y in a headed circular doubly linked list P-


INSERT (X,Y)

LLINK(X)=Y;
RLINK(X)=RLINK(Y);
LLINK(RLINK(Y))=X;
RLINK(Y)=X;

END

insertion

Deletion-

To delete node X from a headed circular doubly linked list P-


DELETE (P,X)

RLINK(LLINK(X))=RLINK(X);
LLINK(RLINK(X))=LLINK(X);

END

deletion

Leave a Reply

Your email address will not be published. Required fields are marked *

*

* Copy This Password *

* Type Or Paste Password Here *

41,650 Spam Comments Blocked so far by Spam Free Wordpress

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>