Data Structures using C

Introduction to Linked Lists

A linked list is a linear data structure made up of nodes. Each node contains data and a pointer that connects it to another node. Linked lists allow dynamic memory allocation and can grow or shrink during program execution.

• Dynamic size
• Nodes connected using pointers
• Efficient insertion and deletion
• Memory allocated at runtime

Node Structure

struct Node{
   int data;
   struct Node* next;
};

Components of a Linked List

• Node → Basic unit of linked list
• Data Field → Stores information
• Pointer Field → Stores next node address
• Head → Starting node
• Tail → Last node

Memory Representation

Unlike arrays, linked list nodes are stored in different memory locations and connected through pointers.

Address     Data     Next
1000         10       2000
2000         20       3000
3000         30       NULL

Need for Linked Lists

Arrays have a fixed size and require contiguous memory locations. If more elements need to be stored than initially allocated, resizing becomes difficult and expensive.

Linked lists solve these problems by allowing memory allocation during runtime. New nodes can easily be inserted or deleted without shifting all existing elements.

• Dynamic memory allocation
• Flexible size
• Efficient insertion and deletion
• Better memory utilization

Creating a Node

Nodes are usually created dynamically using malloc().

struct Node* newNode;

newNode=(struct Node*)
malloc(sizeof(struct Node));

newNode->data=10;
newNode->next=NULL;

Types of Linked Lists

• Singly Linked List
• Doubly Linked List
• Circular Linked List

Singly Linked List

A Singly Linked List is the simplest type of linked list where each node contains data and a pointer to the next node only. Traversal is possible only in the forward direction because there is no link to previous nodes.

Singly linked lists are commonly used when memory efficiency is important because only one pointer field is stored per node.

10 -> 20 -> 30 -> NULL

Doubly Linked List

A Doubly Linked List stores two pointers in each node: one pointer stores the address of the next node and another stores the address of the previous node.

Since nodes can be traversed in both forward and backward directions, insertion and deletion operations become easier. However, additional memory is required because of the extra pointer.

NULL <- 10 <-> 20 <-> 30 -> NULL

Circular Linked List

In a Circular Linked List, the last node does not contain NULL. Instead, the last node points back to the first node, forming a circular chain structure.

Circular linked lists are useful in applications involving cyclic processing such as CPU scheduling, multiplayer games, and round-robin algorithms.

10 -> 20 -> 30
^            |
|____________|

Complexity Analysis

Operation        Complexity

Access            O(n)
Search            O(n)
Insertion         O(1)
Deletion          O(1)

Basic Operations on Linked Lists

Various operations can be performed on linked lists for storing, accessing, and modifying data. These operations are essential for maintaining the linked list structure.

• Creation of nodes
• Insertion of nodes
• Deletion of nodes
• Traversal of nodes
• Searching for elements
• Updating node values
• Sorting linked lists

The basic operations such as traversal, insertion, deletion, searching, and updating are common for all linked list types. However, the implementation of these operations differs depending on whether the linked list is singly, doubly, or circular.

The examples below mainly use a Singly Linked List because it is the simplest and most commonly used implementation for understanding linked list concepts.

Traversal

Traversal means visiting each node one by one from the head node until the end of the linked list is reached.

while(temp!=NULL){
   printf("%d",temp->data);
   temp=temp->next;
}

Time Complexity: O(n)

Searching

Searching is used to locate a particular element in a linked list. Since direct indexing is not available, nodes must be checked one by one.

while(temp!=NULL){

   if(temp->data==key)
      printf("Found");

   temp=temp->next;
}

Time Complexity: O(n)

Insertion

Insertion adds a new node into the linked list. It can be performed at the beginning, end, or any specified position.

newNode->next=head;
head=newNode;

Time Complexity: O(1)

Deletion

Deletion removes a node from the linked list by changing pointer connections between nodes.

head=head->next;

Time Complexity: O(1)

Updating

Updating changes the value stored in an existing node.

temp->data=50;

Arrays vs Linked Lists

• Arrays use contiguous memory
• Linked lists use non-contiguous memory
• Arrays have fixed size
• Linked lists are dynamic
• Arrays provide direct access
• Linked lists require traversal

Applications of Linked Lists

• Stacks and queues
• Browser navigation systems
• Music playlists
• Graph representation
• Dynamic memory allocation

Advantages of Linked Lists

• Dynamic memory allocation
• Efficient insertion and deletion
• No fixed size limitation

Limitations of Linked Lists

• No direct access by index
• Extra memory required for pointers
• Traversal is slower than arrays