Introduction to Linked List

1. It is a data Structure which consists if group of nodes that forms a sequence.
2. It is very common data structure that is used to create tree,graph and other abstract data types.

Linked list comprise of group or list of nodes in which each node have link to next node to form a chain

Linked List definition

1. Linked List is Series of Nodes
2. Each node Consist of two Parts viz Data Part & Pointer Part
3. Pointer Part stores the address of the next node

What is linked list Node ?

1. Each Linked List Consists of Series of Nodes
2. In above Diagram , Linked List Consists of three nodes A,B,C etc
3. Node A has two part one data part which consists of the 5 as data and the second part which contain the address of the next node (i.e it contain the address of the next node)

Linked list Blocks

Linked list is created using following elements –

No	Element	Explanation
1	Node	Linked list is collection of number of nodes
2	Address Field in Node	Address field in node is used to keep address of next node
3	Data Field in Node	Data field in node is used to hold data inside linked list.

We can represent linked list in real life using train in which all the buggies are nodes and two coaches are connected using the connectors.

In case of railway we have peoples seating arrangement inside the coaches is called as data part of lined list while connection between two buggies is address filed of linked list.

Like linked list, trains also have last coach which is not further connected to any of the buggie. Engine can be called as first node of linked list

Advantages of linked list

Firstly understand the basic concept of linked list and take a look at below diagram of linked list –

List of advantages :

1. Linked List is Dynamic data Structure .
2. Linked List can grow and shrink during run time.
3. Insertion and Deletion Operations are Easier
4. Efficient Memory Utilization ,i.e no need to pre-allocate memory
5. Faster Access time,can be expanded in constant time without memory overhead
6. Linear Data Structures such as Stack,Queue can be easily implemeted using Linked list

Drawbacks / Disadvantages of Linked List

1. Wastage of Memory –

1. Pointer Requires extra memory for storage.
2. Suppose we want to store 3 integer data items then we have to allocate memory –

in case of array –

Memory Required in Array = 3 Integer * Size
                         = 3 * 2 bytes
                         = 6 bytes

in case of array –

Memory Required in LL    = 3 Integer * Size of Node
                         = 3 * Size of Node Structure
                         = 3 * Size(data + address pointer)
                         = 3 * (2 bytes + x bytes)
                         = 6 bytes + 3x bytes

*x is size of complete node structure it may vary

2. No Random Access

1. In array we can access nth element easily just by using a[n].
2. In Linked list no random access is given to user, we have to access each node sequentially.
3. Suppose we have to access nth node then we have to traverse linked list n times.

Suppose Element is present at the starting location then –

We can access element in first Attempt

Suppose Element is present at the Last location then –

We can access element in last Attempt

3 . Time Complexity

1. Array can be randomly accessed , while the Linked list cannot be accessed Randomly
2. Individual nodes are not stored in the contiguous memory Locations.
3. Access time for Individual Element is O(n) whereas in Array it is O(1).

4. Reverse Traversing is difficult

1. In case if we are using singly linked list then it is very difficult to traverse linked list from end.
2. If using doubly linked list then though it becomes easier to traverse from end but still it increases again storage space for back pointer.

5. Heap Space Restriction

1. Whenever memory is dynamically allocated , It utilizes memory from heap.
2. Memory is allocated to Linked List at run time if and only if there is space available in heap.
3. If there is insufficient space in heap then it won’t create any memory.

Difference Between array and Linked List : Array Vs Linked List

1. Access :Random / Sequential

• Stack elements can be randomly Accessed using Subscript Variable
• e.g a[0],a[1],a[3] can be randomly accessed
• While In Linked List We have to Traverse Through the Linked List for Accessing Element. So O(n) Time required for Accessing Element .
• Generally In linked List Elements are accessed Sequentially.

2 . Memory Structure :

• Stack is stored in contiguous Memory Locations , i.e Suppose first element is Stored at 2000 then Second Integer element will be stored at 2002 .
• But It is not necessary to store next element at the Consecutive memory Location .
• Element is stored at any available Location , but the Pointer to that memory location is stored in Previous Node.

3 . Insertion / Deletion

• As the Array elements are stored in Consecutive memory Locations , so While Inserting elements ,we have to create space for Insertion.
• So More time required for Creating space and Inserting Element
• Similarly We have to Delete the Element from given Location and then Shift All successive elements up by 1 position
• In Linked List we have to Just Change the Pointer address field (Pointer),So Insertion and Deletion Operations are quite easy to implement

4 . Memory Allocation :

• Memory Should be allocated at Compile-Time in Stack . i.e at the time when Programmer is Writing Program
• In Linked list memory can be allocated at Run-Time , i.e After executing Program
• Stack uses Static Memory Allocation and Linked List Uses Dynamic Memory Allocation
• Dynamic Memory allocation functions – malloc,calloc,delete etc…

Singly Linked List : C Programming Data Structure

1. In this type of Linked List two successive nodes are linked together in linear fashion .
2. Each Node contain address of the next node to be followed.
3. In Singly Linked List only Linear or Forward Sequential  movement is possible.
4. Elements are accessed sequentially , no direct access is allowed.

Explanation :

1. It is most basic type of Linked List in C.
2. It is simple sequence of Dynamically allocated Nodes.
3. Each Node has its successor and predecessor.
4. First Node does not have predecessor while last node does not have any successor.
5. Last Node have successor reference as “NULL“.
6. In the above Linked List We have 3 types of nodes.

1.First Node
2.Last Node
3.Intermediate Nodes

7. In Singly Linked List access is given only in one direction thus Accessing Singly Linked is Unidirectional.
8. We can have multiple data fields inside Node but we have only single “Link” for next node.

Doubly Linked List : Traverse Bi-directional

1. In Doubly Linked List , each node contain two address fields .
2. One address field for storing address of next node to be followed and second address field contain address of previous node linked to it.
3. So Two way access is possible i.e We can start accessing nodes from start as well as from last .
4. Like Singly Linked List also only Linear but Bidirectional  Sequential  movement is possible.
5. Elements are accessed sequentially , no direct access is allowed.

Explanation :

1. Doubly Linked List is most useful type of Linked List.
2. In DLL we have facility to access both next as well as previous data using “next link” and “previous link“.
3. In the above diagram , suppose we are currently on 2nd node i.e at 4 then we can access next and previous data using –

To Access Next Data : curr_node->next->data

To Access Previous Data : curr_node->previous->data

4. We have to always maintain start node , because it is the only node that is used to keep track of complete linked list.

Circular Linked List

1. Circular Linked List is Divided into 2 Categories .
• Singly Circular Linked List
• Doubly Circular Linked List
2. In Circular Linked List Address field of Last node contain address of “First Node“.
3. In short First Node and Last Nodes are adjacent .
4. Linked List is made circular by linking first and last node , so it looks like circular chain [ shown in Following diagram ].
5. Two way access is possible only if we are using “Doubly Circular Linked List”
6. Sequential  movement is possible
7. No direct access is allowed.