Linked Lists in Data Structures

What is a Linked List?

A linked list is a linear data structure where elements are stored in nodes that are connected using pointers or references. Each node contains two parts: data and a reference to the next node. This structure allows for efficient insertions and deletions as it doesn't require the elements to be stored in contiguous memory locations.

Visual Representation of a Linked List

Types of Linked Lists

Linked lists come in several variations, each with its own advantages and use cases:

Common Linked List Operations

Let's explore the most common operations performed on linked lists and their time complexities:

Linked List Implementation

Let's look at how to implement a simple singly linked list in different programming languages:

1#include <stdio.h>
2#include <stdlib.h>
3
4// Define the structure for a node
5struct Node {
6    int data;
7    struct Node* next;
8};
9
10// Function to create a new node
11struct Node* createNode(int data) {
12    struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
13    if (newNode == NULL) {
14        printf("Memory allocation failed\n");
15        exit(1);
16    }
17    newNode->data = data;
18    newNode->next = NULL;
19    return newNode;
20}
21
22// Function to insert a node at the beginning
23struct Node* insertAtBeginning(struct Node* head, int data) {
24    struct Node* newNode = createNode(data);
25    newNode->next = head;
26    return newNode;
27}
28
29// Function to display the linked list
30void displayList(struct Node* head) {
31    struct Node* current = head;
32    
33    if (current == NULL) {
34        printf("List is empty\n");
35        return;
36    }
37    
38    printf("Linked List: ");
39    while (current != NULL) {
40        printf("%d -> ", current->data);
41        current = current->next;
42    }
43    printf("NULL\n");
44}
45
46// Function to free the memory
47void freeList(struct Node* head) {
48    struct Node* temp;
49    while (head != NULL) {
50        temp = head;
51        head = head->next;
52        free(temp);
53    }
54}
55
56int main() {
57    struct Node* head = NULL;
58    
59    // Insert nodes
60    head = insertAtBeginning(head, 30);
61    head = insertAtBeginning(head, 20);
62    head = insertAtBeginning(head, 10);
63    
64    // Display the list
65    displayList(head);
66    
67    // Free memory
68    freeList(head);
69    
70    return 0;
71}

Linked Lists vs. Arrays

When deciding between linked lists and arrays, consider their relative strengths and weaknesses:

Applications of Linked Lists

Linked lists are used in a variety of applications across computer science:

• Implementation of other data structures - Stacks, queues, and hash tables can be implemented using linked lists.
• Dynamic memory allocation - Operating systems use linked lists to manage memory blocks.
• Undo functionality - Applications use linked lists to implement undo operations.
• Symbol tables in compilers - Linked lists can be used to implement symbol tables.
• Adjacency lists for graphs - Graph representations often use linked lists for storing adjacent vertices.
• Music player playlists - Circular linked lists can be used to play songs in a loop.

Next Steps

Now that you understand linked lists, you're ready to explore more complex data structures:

• Stacks-Learn about the Last-In-First-Out (LIFO) data structure
• Queues-Discover the First-In-First-Out (FIFO) data structure
• Trees-Explore hierarchical data structures