Linked List and its Function

Linked List

Like arrays, Linked List is a linear data structure. Unlike arrays, linked list elements are not stored at a contiguous location; the elements are linked using pointers.

Why Linked List?

Arrays can be used to store linear data of similar types, but arrays have the following limitations.

1) The size of the arrays is fixed: So we must know the upper limit on the number of elements in advance. Also, generally, the allocated memory is equal to the upper limit irrespective of the usage.

2) Inserting a new element in an array of elements is expensive because the room has to be created for the new elements and to create room existing elements have to be shifted.

Advantages over arrays

1) Dynamic size

2) Ease of insertion/deletion

Representation:

A linked list is represented by a pointer to the first node of the linked list. The first node is called the head. If the linked list is empty, then the value of the head is NULL.

Each node in a list consists of at least two parts:

1) data

2) Pointer (Or Reference) to the next node

In C, we can represent a node using structures. Below is an example of a linked list node with integer data.

In Java or C#, LinkedList can be represented as a class and a Node as a separate class. The LinkedList class contains a reference of Node class type.

Linked List Traversal

In the previous program, we have created a simple linked list with three nodes. Let us traverse the created list and print the data of each node. For traversal, let us write a general-purpose function printList() that prints any given list.

Circular Singly Linked List

Why Circular? In a singly linked list, for accessing any node of linked list, we start traversing from the first node. If we are at any node in the middle of the list, then it is not possible to access nodes that precede the given node. This problem can be solved by slightly altering the structure of singly linked list. In a singly linked list, next part (pointer to next node) is NULL, if we utilize this link to point to the first node then we can reach preceding nodes. Refer this for more advantages of circular linked lists.

The structure thus formed is circular singly linked list look like this:

In this post, implementation and insertion of a node in a Circular Linked List using singly linked list are explained.

Implementation

To implement a circular singly linked list, we take an external pointer that points to the last node of the list. If we have a pointer last pointing to the last node, then last -> next will point to the first node.

The ponter last points to node Z and last -> next points to node P.

Insertion in an empty List

Initially when the list is empty, last pointer will be NULL.

After inserting a node T,

After insertion, T is the last node so pointer last points to node T. And Node T is first and last node, so T is pointing to itself.

Doubly 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 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.

Insertion

A node can be added in four ways :

1) At the front of the DLL

2) After a given node.

3) At the end of the DLL

4) Before a given node.

Doubly Circular 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.

Insertion in Circular Doubly Linked List

1. Insertion at the end of list or in an empty list

• Empty List (start = NULL): A node(Say N) is inserted with data = 5, so previous pointer of N points to N and next pointer of N also points to N. But now start pointer points to the first node the list.

• List initially contain some nodes, start points to first node of the List: A node(Say M) is inserted with data = 7, so previous pointer of M points to last node, next pointer of M points to first node and last node’s next pointer points to this M node and first node’s previous pointer points to this M node.

2. Insertion at the beginning of the list: To insert a node at the beginning of the list, create a node(Say T) with data = 5, T next pointer points to first node of the list, T previous pointer points to last node the list, last node’s next pointer points to this T node, first node’s previous pointer also points this T node and at last don’t forget to shift ‘Start’ pointer to this T node.

3. Insertion in between the nodes of the list: To insert a node in between the list, two data values are required one after which new node will be inserted and another is the data of the new node.

Following are advantages and disadvantages of circular doubly linked list:

Advantages:

• List can be traversed from both the directions i.e. from head to tail or from tail to head.
• Jumping from head to tail or from tail to head is done in constant time O(1).
• Circular Doubly Linked Lists are used for implementation of advanced data structures like Fibonacci Heap.

Disadvantages

• It takes slightly extra memory in each node to accommodate previous pointer.
• Lots of pointers involved while implementing or doing operations on a list. So, pointers should be handled carefully otherwise data of the list may get lost.

Applications of Circular doubly linked list

• Managing songs playlist in media player applications.
• Managing shopping cart in online shopping.

Source :

https://www.geeksforgeeks.org/circular-singly-linked-list-insertion/

https://en.wikipedia.org/wiki/Linked_list

https://www.geeksforgeeks.org/linked-list-set-1-introduction/

https://www.geeksforgeeks.org/doubly-circular-linked-list-set-1-introduction-and-insertion/

https://binusmaya.binus.ac.id/