Vincent Weilasto / 2301889312 / CA01

After arrays, the second most popular data structure is Linked List. A linked list is a linear data structure, made of a chain of nodes in which each node contains a value and a pointer to the next node in the chain. In this article, let’s see how to implement a linked list in C.

What is Linked List in C?

A Linked List is a linear data structure. Every linked list has two parts, the data section and the address section that holds the address of the next element in the list, which is called a node.

The size of the linked list is not fixed, and data items can be added at any locations in the list. The disadvantage is that to get to a node, we must traverse to all the way from the first node to the node that we require. The Linked List is like an array but unlike an array, it is not stored sequentially in the memory.

The most popular types of a linked list are:

Singly link list
Doubly link list

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.

Introduction to Linked Lists

Linked List is a very commonly used linear data structure which consists of group of nodes in a sequence.

Each node holds its own data and the address of the next node hence forming a chain like structure.

Linked Lists are used to create trees and graphs.

Advantages of Linked Lists

They are a dynamic in nature which allocates the memory when required.
Insertion and deletion operations can be easily implemented.
Stacks and queues can be easily executed.
Linked List reduces the access time.

Disadvantages of Linked Lists

The memory is wasted as pointers require extra memory for storage.
No element can be accessed randomly; it has to access each node sequentially.
Reverse Traversing is difficult in linked list.

Applications of Linked Lists

Linked lists are used to implement stacks, queues, graphs, etc.
Linked lists let you insert elements at the beginning and end of the list.
In Linked Lists we don't need to know the size in advance.

Linked List Representation

Linked list can be visualized as a chain of nodes, where every node points to the next node.

As per the above illustration, following are the important points to be considered.

Linked List contains a link element called first.
Each link carries a data field(s) and a link field called next.
Each link is linked with its next link using its next link.
Last link carries a link as null to mark the end of the list.

Basic Operations

Following are the basic operations supported by a list.

Insertion − Adds an element at the beginning of the list.
Deletion − Deletes an element at the beginning of the list.
Display − Displays the complete list.
Search − Searches an element using the given key.
Delete − Deletes an element using the given key.

Types of Linked Lists

There are 3 different implementations of Linked List available, they are:

Singly Linked List

Doubly Linked List

Circular Linked List

Let's know more about them and how they are different from each other.

Singly Linked List

Singly linked lists contain nodes which have a data part as well as an address part i.e. `next`, which points to the next node in the sequence of nodes.

The operations we can perform on singly linked lists are insertion, deletion and traversal.

Here is the source code of single linked list :

1. Make sure that we create this, this is a single linked list.

2. Here is the algorithm to insert at the beginning in single linked list :

3. Here is the algorithm to insert at the end in single linked list :

4 Here is the algorithm to delete at the beginning in single linked list :

5. Here is the algorithm to delete at the end in single linked list :

6. Here is the algorithm to view a data in single linked list :

If want to see another source code, you can see it from :

Inserting a node in single linked list :

https://www.geeksforgeeks.org/linked-list-set-2-inserting-a-node/

Deleting a node in single linked list :

https://www.geeksforgeeks.org/linked-list-set-3-deleting-node/

Inserting and Deleting a node in single linked list :

https://socs.binus.ac.id/2017/03/15/single-linked-list/

Doubly Linked List

In a doubly linked list, each node contains a data part and two addresses, one for the previous node and one for the next node.

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.

Here is the example of source code in double linked list :

1. Make sure that we create this, this is a double linked list.

2. Here is the algorithm to insert at the beginning in double linked list :

3. Here is the algorithm to insert at the end in double linked list :

4. Here is the algorithm to delete from the beginning in double linked list :

5. Here is the algorithm to view from front of the data until behind the data in double linked list :

6. Here is the algorithm to view from behind the data until front of the data in double linked list :

7. Now we Called the function at int main function :

8. This is the Output :

If want to see another source code, you can see it from :

Introduction and insertion in double linked list :

https://www.geeksforgeeks.org/doubly-linked-list/

Deletion in double linked list :

https://www.geeksforgeeks.org/delete-a-node-in-a-doubly-linked-list/

Circular Linked List

In circular linked list the last node of the list holds the address of the first node hence forming a circular chain.

There are Circular singly linked list and Circular doubly linked list, let's see how it looks.

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:

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.

Why have we taken a pointer that points to the last node instead of first node ?
For insertion of node in the beginning we need traverse the whole list. Also, for insertion and the end, the whole list has to be traversed. If instead of start pointer we take a pointer to the last node then in both the cases there won’t be any need to traverse the whole list. So insertion in the begging or at the end takes constant time irrespective of the length of the list.

Insertion
A node can be added in three ways:

Insertion in an empty list
Insertion at the beginning of the list
Insertion at the end of the list
Insertion in between the nodes

If want to see source code, you can see it from :

Insertion in circular single linked list :

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

Deletion in circular single linked list :

https://www.geeksforgeeks.org/deletion-circular-linked-list/

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.

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
};