Data Struct Linked List 2

Nama: Dea Claresta

Nim: 2301863736

1.      Circular single linked list

Circular linked list is a linked list where all nodes are connected to form a circle. There is no NULL at the end. A circular linked list can be a singly circular linked list or doubly circular linked list.

Advantages of Circular Linked Lists:
1) Any node can be a starting point. We can traverse the whole list by starting from any point. We just need to stop when the first visited node is visited again.

2) Useful for implementation of queue. Unlike this  implementation, we don’t need to maintain two pointers for front and rear if we use circular linked list. We can maintain a pointer to the last inserted node and front can always be obtained as next of last.

3) Circular lists are useful in applications to repeatedly go around the list. For example, when multiple applications are running on a PC, it is common for the operating system to put the running applications on a list and then to cycle through them, giving each of them a slice of time to execute, and then making them wait while the CPU is given to another application. It is convenient for the operating system to use a circular list so that when it reaches the end of the list it can cycle around to the front of the list.

4) Circular Doubly Linked Lists are used for implementation of advanced data structures like Fibonacci Heap. (Geeks for Geeks)

2.     Double linked list

A Doubly Linked List (DLL) contains an extra pointer, typically called previous pointer, together with next pointer and data which are there in singly linked list.

Following is representation of a DLL node in C language.

/* Node of a doubly linked list */ struct Node {     int data;     struct Node* next; // Pointer to next node in DLL     struct Node* prev; // Pointer to previous node in DLL };

Following are advantages/disadvantages of doubly linked list over singly linked list.

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 (See this and this).
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. (Geeks for Geeks)

3.     Circular doubly linked list

Circular Doubly Linked List has properties of both doubly linked list and circular linked list in which two consecutive elements are linked or connected by previous and next pointer and the last node points to first node by next pointer and also the first node points to last node by previous pointer.

Following is representation of a Circular doubly linked list node in C/C++:

// Structure of the node

struct node

{

    int data;

    struct node *next; // Pointer to next node

    struct node *prev; // Pointer to previous node

};

(Geeks for Geeks)

Bibliography

Geeks for Geeks. (n.d.). Retrieved from Circular Linked List | Set 1 (Introduction and Applications): https://www.geeksforgeeks.org/circular-linked-list/

Geeks for Geeks. (n.d.). Retrieved from Doubly Linked List | Set 1 (Introduction and Insertion): https://www.geeksforgeeks.org/doubly-linked-list/

Geeks for Geeks. (n.d.). Retrieved from Doubly Circular Linked List | Set 1 (Introduction and Insertion): https://www.geeksforgeeks.org/doubly-circular-linked-list-set-1-introduction-and-insertion/