CSLL (Cyclic Singly Linked List)

 

	struct node {
	   eltType elt;                 /* field to store an element */
	   struct node* next;           /* pointer to the next node */
	};
	typedef struct node listNode;
	typedef listNode*   listPtr;
	typedef listPtr     list;

	list L;                         /* L is a variable of type list */
	                                /* L is a pointer to some listNode */
	                       
Since the list is cyclic each node can be reached from any arbitrarily chosen node. Thus, the access pointer can be 
a pointer to any node in the list and the notion of first is no longer strictly needed. This also holds for the CSLL 
defined with a header node. Sometimes however the notion of first and last is convenient and in that case last will 
give access to the list and first is the successor of last.

	

                     
	struct node {
	   eltType	 elt;      /* field to store an element */
	   struct node* next;  /* pointer to the next node */
	};
	typedef struct node listNode;
	typedef listNode*   listPtr;
	
	typedef header {
	   listPtr cur;
	   listPtr last;
	   int     size;
	};
	typedef struct header listHeader;
	typedef listHeader* list;

	list L;                /* L is a variable of type list */
	                       /* L is a pointer to the header node */

	

	

OUTPUT:

=> HC 21.27

DLL (Doubly Linked List)

	

Each node contains two fields next and prev. Next connects the node to its successor and prev points to its predecessor. 
This symmetric design is a real bi-directional design: the list can now be traversed from right to left as easy as from 
left to right. As a consequence any insert and delete operation can be implemented in a very simple way at the cost of 
updating several pointers instead of only one. 
	
The declaration of a DLL without a header node has the following appearance: 

                                                 /* DLL = Doubly Linked List */
                                                      /* without header node */
	struct node {
	   eltType	 elt;      /* field to store an element */
	   struct node* next;  /* pointer to the next node */
	   struct node* prev;  /* pointer to the previous node */
	};
	typedef struct node listNode;
	typedef listNode*   listPtr;
	typedef listPtr     list;
	
	list L;                /* L is a variable of type list */
	                       /* L is a pointer to some listnode */

If a header node is used we declare: 
	
	struct header {
	   listPtr first;
	   listPtr cur;
	   listPtr last;
	   int     size;
	};
	typedef struct header listHeader;
	typedef listHeader* list;
	
	list L;                /* L is a variable of type list */
	                       /* L is a pointer to the header node */

The ease with which the insert and delete operations can be performed using a DLL are illustrated in the next four pictures.

	

	

	

	

OUTPUT:

=> HC 21.28

CDLL (Cyclic Doubly Linked List)

The last and most luxurious variation in the design of lists is the CDLL (Cyclic Doubly Linked List) with a header.

	

PRACTICUM: 
Write a declaration for a CDLL with header where the nodes contain a 
pointer to element and the element contains a key and a pointer to data.

OUTPUT:

=> HC 21.28