Introduction to Linked Lists

A linked list is a linear data structure composed of nodes. Each node contains a data field and a pointer (or reference) pointing to the next node. Nodes in a linked list are dynamically allocated in memory, unlike arrays which require pre-allocated fixed sizes, thereby offering greater flexibility.

Structure of Linked Lists

Each node in a linked list typically consists of two parts:

  • Data Field: Stores actual data (such as integers, strings, etc.)
  • Pointer Field: Contains the address (or reference) of the next node

The structure of a linked list can be represented as:

Node1 → Node2 → Node3 → ... → Noden

In this representation, the pointer field of each node points to the next node, and the pointer field of the last node is typically NULL, indicating the end of the list.

Implementation of Linked Lists

The implementation of a linked list usually involves dynamic memory allocation, creating nodes via functions like malloc or new. For example, in C language, the structure of a node might be defined as follows:

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

The process of creating a linked list includes initializing a head node and subsequently adding new nodes one by one. For example:

struct Node* head = NULL;  
struct Node* new_node = (struct Node*)malloc(sizeof(struct Node));  
new_node->data = 10;  
new_node->next = NULL;  
head = new_node;

Characteristics of Linked Lists

Linked lists possess the following characteristics:

  1. Dynamic Nature: The number of nodes can grow or shrink dynamically without the need for pre-allocating memory.
  2. Flexibility: Supports fast insertion and deletion operations without the need to adjust other nodes.
  3. No Fixed Size: Memory requirements are allocated dynamically based on the actual amount of data.
  4. Difficulty in Random Access: Nodes cannot be accessed directly via an index; traversal is required to reach specific elements.

Common Operations on Linked Lists

The core operations on a linked list include:

  • Traversal: Starting from the head node, accessing the data of each node sequentially.
  • Insertion: Inserting a new node at a specified position, which requires adjusting the pointer fields of adjacent nodes.
  • Deletion: Removing a specified node, which also requires adjusting the pointer fields of adjacent nodes.
  • Search: Searching for a node containing specific data by traversing the linked list.

Application Scenarios of Linked Lists

Linked lists are widely used in scenarios requiring dynamic data management, such as:

  • Operating Systems: Process management, memory allocation.
  • Database Systems: Index structures, dynamic table management.
  • Graph Representation: Implementation of adjacency lists for graphs.
  • Stacks and Queues: Implementing dynamic stack and queue structures using linked lists.

Pros and Cons of Linked Lists

Advantages:

  • High space efficiency with better memory utilization.
  • Supports dynamic expansion without pre-allocating memory.
  • Efficient insertion and deletion operations.

Disadvantages:

  • Slower access speed, requiring sequential traversal.
  • Higher management complexity due to the need to handle pointer references.

Implementation Example of Linked Lists

The following is a simple implementation example of a linked list (C language):

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

void append(struct Node** head, int data) {
    struct Node* new_node = (struct Node*)malloc(sizeof(struct Node));
    new_node->data = data;
    new_node->next = NULL;
    if (*head == NULL) {
        *head = new_node;
    } else {
        new_node->next = *head;
        *head = new_node;
    }
}

This function dynamically allocates memory to insert a new node at the end of the linked list.