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-
[cpp]
INSERT (X,Y)
LLINK(X)=Y;
RLINK(X)=RLINK(Y);
LLINK(RLINK(Y))=X;
RLINK(Y)=X;
END
[/cpp]
Deletion-
To delete node X from a headed circular doubly linked list P-
[cpp]
DELETE (P,X)
RLINK(LLINK(X))=RLINK(X);
LLINK(RLINK(X))=LLINK(X);
END
[/cpp]
