Lesson 07-C Language Linked List Operations

A linked list is a linear data structure where elements are not stored contiguously in memory but are linked together using pointers. Each element in a linked list is called a node, and each node consists of two parts: the data part and the pointer part. The data part stores the actual data, while the pointer part points to the next node in the list. This structure of linked lists provides dynamic memory allocation, making it easy to insert or delete elements at any position in the list.

Basic Usage of Linked Lists

Core Structure of a Linked List

A linked list consists of multiple nodes, each containing two parts:

  • Data field: Stores actual data (such as integers, structs, etc.).
  • Pointer field: Stores the memory address of the next (or previous) node.

Comparison of Common Linked List Types

TypePointer DesignFeaturesApplicable Scenarios
Singly Linked ListOnly next pointer (to next node)Simple structure, low memory usageSequential access, tail insertion dominant
Doubly Linked Listprev (predecessor) + next (successor) pointersSupports bidirectional traversal, more efficient insertion/deletionFrequent insertion/deletion, bidirectional access needed
Circular Linked ListTail node’s next points to head nodeConnected head-to-tail, no clear start/endCircular traversal, ring-shaped data structures

Basic Types of Linked Lists

  • Singly Linked List: Each node contains only one pointer to the next node.
  • Doubly Linked List: Each node contains two pointers, one to the previous node and one to the next node.
  • Circular Linked List: The last node’s pointer points to the head node, forming a closed loop.

Creating a Linked List Node

First, define a struct to represent a node in the linked list. The struct typically includes a data member and a pointer to the next node.

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

Basic Operations on Linked Lists

1. Create a new node: Use malloc() to dynamically allocate memory for a new node.

   struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
   newNode->data = 5;
   newNode->next = NULL;

2. Insert a node:

  • Insert at head: The new node’s next pointer points to the current head, then update the head pointer.
  • Insert at tail: Traverse the list to find the last node, then point its next to the new node.
  • Insert in middle: Find the appropriate node and insert the new node after it.

3. Delete a node: Find the node before the one to delete, point its next to the node after the target, then free the target node’s memory.

4. Search for a node: Traverse the list until the target node is found or the end is reached.

5. Traverse the list: Start from the head node, use a temporary pointer to traverse until NULL.

The following is a simple singly linked list implementation including insertion and traversal:

#include <stdio.h>
#include <stdlib.h>

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

// Insert new node at the head of the list
void insertAtHead(struct Node** head, int data) {
    struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
    newNode->data = data;
    newNode->next = *head;
    *head = newNode;
}

// Print the list
void printList(struct Node* head) {
    struct Node* temp = head;
    while (temp != NULL) {
        printf("%d -> ", temp->data);
        temp = temp->next;
    }
    printf("NULL\n");
}

int main() {
    struct Node* head = NULL;

    insertAtHead(&head, 10);
    insertAtHead(&head, 20);
    insertAtHead(&head, 30);

    printList(head);

    return 0;
}

Singly Linked List

A singly linked list is a linear data structure where elements are connected via pointers. Each element (node) consists of two parts: one for storing data and a pointer to the next element. The last element’s pointer in a singly linked list points to NULL, indicating the end of the list.

Node Structure of a Singly Linked List

First, define the node structure for a singly linked list. A typical node structure is as follows:

typedef struct Node {
    int data;       // Data field
    struct Node* next; // Pointer to next node
} Node;

Here, data is the data stored in the node, and next is the pointer to the next node in the list.

Basic Operations on Singly Linked List

Basic operations on a singly linked list include:

1. Create node: Use malloc to allocate memory and initialize the node. 2. Insert node:

  • Insert at the head of the list
  • Insert at the tail of the list
  • Insert at a specific position

3. Delete node: Find the node and update pointer connections. 4. Search node: Traverse the list until the target node is found. 5. Traverse list: Visit each node sequentially from the head until NULL. 6. Free list: Release memory of all nodes in the list.

Create Node

Dynamically allocate memory and initialize the node, returning the node pointer.

// Create a new node (with value val)
Node* create_node(int val) {
    Node* new_node = (Node*)malloc(sizeof(Node));  // Allocate memory
    if (new_node == NULL) {                        // Handle allocation failure
        perror("malloc failed");
        exit(EXIT_FAILURE);
    }
    new_node->data = val;   // Initialize data field
    new_node->next = NULL;  // Initially no next node
    return new_node;
}

Insert Node

Insertion operations include head insertion, tail insertion, and insertion at a specific position.

(1) Head Insertion (Insert at the head of the list)

The new node becomes the new head, and the original head becomes its successor.

// Head insertion: Insert new node at the head of the list
void insert_at_head(Node** head, int val) {
    Node* new_node = create_node(val);  // Create new node
    new_node->next = *head;             // New node's next points to original head
    *head = new_node;                   // Update head pointer to new node
}
(2) Tail Insertion (Insert at the tail of the list)

Find the last node in the list and point its next to the new node.

// Tail insertion: Insert new node at the tail of the list
void insert_at_tail(Node** head, int val) {
    Node* new_node = create_node(val);  // Create new node
    if (*head == NULL) {                // If list is empty, new node becomes head
        *head = new_node;
        return;
    }
    Node* current = *head;              // Find the last node
    while (current->next != NULL) {
        current = current->next;
    }
    current->next = new_node;           // Last node's next points to new node
}
(3) Insert at Specific Position (Insert after the n-th node)

Traverse the list to find the n-th node and adjust pointers to complete insertion.

// Insert at position: Insert new node after the n-th node (n starts from 0)
int insert_at_position(Node** head, int n, int val) {
    if (n < 0) return 0;  // Invalid position
    if (n == 0) {         // Equivalent to head insertion
        insert_at_head(head, val);
        return 1;
    }
    Node* current = *head;
    for (int i = 0; i < n - 1; i++) {  // Find the (n-1)-th node
        if (current == NULL) return 0; // List length less than n
        current = current->next;
    }
    if (current == NULL) return 0;     // List length less than n
    Node* new_node = create_node(val); // Create new node
    new_node->next = current->next;    // New node's next points to original n-th node
    current->next = new_node;          // (n-1)-th node's next points to new node
    return 1;
}

Delete Node

Deletion operations include deletion by value and deletion by position, requiring finding the predecessor of the target node to adjust pointers.

(1) Delete by Value (Delete first node with value val)

Traverse the list to find the target node and delete it if found.

// Delete by value: Delete the first node with value val
int delete_by_value(Node** head, int val) {
    if (*head == NULL) return 0;  // List is empty
    Node* current = *head;
    Node* prev = NULL;            // Record predecessor
    while (current != NULL) {
        if (current->data == val) {
            if (prev == NULL) {    // Target is head node
                *head = current->next;
            } else {
                prev->next = current->next;  // Predecessor's next points to target's next
            }
            free(current);  // Free memory
            return 1;
        }
        prev = current;
        current = current->next;
    }
    return 0;  // Target not found
}
(2) Delete by Position (Delete the n-th node)

Find the predecessor of the n-th node, adjust pointers, and free memory.

// Delete by position: Delete the n-th node (n starts from 0)
int delete_by_position(Node** head, int n) {
    if (n < 0 || *head == NULL) return 0;  // Invalid position or empty list
    if (n == 0) {  // Delete head node
        Node* temp = *head;
        *head = (*head)->next;
        free(temp);
        return 1;
    }
    Node* current = *head;
    Node* prev = NULL;
    for (int i = 0; i < n; i++) {  // Find the n-th node
        prev = current;
        current = current->next;
        if (current == NULL) return 0;  // List length less than n
    }
    prev->next = current->next;  // Predecessor's next points to target's next
    free(current);               // Free memory
    return 1;
}

Traverse List

Start from the head node and visit each node’s data field until NULL.

// Traverse and print all node data
void traverse_list(Node* head) {
    Node* current = head;
    while (current != NULL) {
        printf("%d -> ", current->data);
        current = current->next;
    }
    printf("NULL\n");
}

Search Node (by value)

Traverse the list and return the first node with value val (or NULL if not found).

// Search by value: Return first node with value val
Node* find_by_value(Node* head, int val) {
    Node* current = head;
    while (current != NULL) {
        if (current->data == val) {
            return current;
        }
        current = current->next;
    }
    return NULL;  // Not found
}

Simple Singly Linked List Implementation

Below is a simple singly linked list implementation including creation, insertion, and traversal:

#include <stdio.h>
#include <stdlib.h>

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

// Create new node
Node* createNode(int data) {
    Node* newNode = (Node*)malloc(sizeof(Node));
    if (newNode == NULL) {
        printf("Memory allocation failed!\n");
        exit(1);
    }
    newNode->data = data;
    newNode->next = NULL;
    return newNode;
}

// Insert node at the end of the list
void insertAtEnd(Node** head, int data) {
    Node* newNode = createNode(data);
    if (*head == NULL) {
        *head = newNode;
        return;
    }
    Node* last = *head;
    while (last->next != NULL) {
        last = last->next;
    }
    last->next = newNode;
}

// Print the list
void printList(Node* head) {
    Node* temp = head;
    while (temp != NULL) {
        printf("%d -> ", temp->data);
        temp = temp->next;
    }
    printf("NULL\n");
}

int main() {
    Node* head = NULL;

    insertAtEnd(&head, 10);
    insertAtEnd(&head, 20);
    insertAtEnd(&head, 30);

    printList(head);

    return 0;
}

Notes for Singly Linked List

  • Memory Management: Check if malloc succeeds when inserting; always free memory after deletion to avoid leaks.
  • Pointer Validity: Check if pointer is NULL before accessing current->next.
  • Head Pointer Protection: Use double pointer (Node** head) to modify the head pointer during insertion/deletion.
  • Boundary Conditions: Handle special cases like empty list (head == NULL) or single-node list.

Doubly Linked List

A doubly linked list is a more flexible type of linked list where each node contains not only a pointer to the next node but also a pointer to the previous node. This bidirectional linking makes moving forward and backward equally easy and simplifies insertion and deletion since you don’t need to traverse from the head to find the previous node.

Node Structure of a Doubly Linked List

The node of a doubly linked list is typically defined as follows:

typedef struct Node {
    int data;       // Data field
    struct Node* next; // Pointer to next node
    struct Node* prev; // Pointer to previous node
} Node;

Basic Operations on Doubly Linked List

Basic operations are similar to singly linked lists, but with key differences:

1. Create node: Use malloc to allocate memory and initialize the node. 2. Insert node:

  • Insert at head: New node’s prev points to NULL, next to current head; current head’s prev points to new node; update head to new node.
  • Insert at tail: New node’s next points to NULL, prev to current tail; current tail’s next points to new node.
  • Insert in middle: Find position, update next and prev of adjacent nodes.

3. Delete node: Update next of previous node and prev of next node, then free the node. 4. Search node: Traverse from head until target is found or end is reached. 5. Traverse list: Traverse forward from head to NULL; or backward from tail. 6. Free list: Release memory of all nodes.

Create Node

Similar to singly linked list, but initialize both prev and next to NULL.

// Create new doubly linked list node (with value val)
DNode* create_dnode(int val) {
    DNode* new_node = (DNode*)malloc(sizeof(DNode));
    if (new_node == NULL) {
        perror("malloc failed");
        exit(EXIT_FAILURE);
    }
    new_node->data = val;
    new_node->prev = NULL;  // Initially no predecessor
    new_node->next = NULL;  // Initially no successor
    return new_node;
}

Insert Node

Insertion requires updating both predecessor and successor pointers, supporting head insertion, tail insertion, and insertion at position.

(1) Head Insertion

New node becomes head, original head’s prev points to new node.

// Head insertion: Insert new node at the head of the doubly linked list
void dinsert_at_head(DNode** head, int val) {
    DNode* new_node = create_dnode(val);
    if (*head == NULL) {                // Empty list, new node becomes head
        *head = new_node;
        return;
    }
    new_node->next = *head;             // New node's next points to original head
    (*head)->prev = new_node;           // Original head's prev points to new node
    *head = new_node;                   // Update head to new node
}
(2) Tail Insertion

Find tail node, new node’s prev points to tail, tail’s next points to new node.

// Tail insertion: Insert new node at the tail of the doubly linked list
void dinsert_at_tail(DNode** head, int val) {
    DNode* new_node = create_dnode(val);
    if (*head == NULL) {                // Empty list, new node becomes head
        *head = new_node;
        return;
    }
    DNode* current = *head;
    while (current->next != NULL) {     // Find tail node
        current = current->next;
    }
    current->next = new_node;           // Tail's next points to new node
    new_node->prev = current;           // New node's prev points to tail
}
(3) Insert at Specific Position (Insert after the n-th node)

Find the n-th node and update predecessor and successor pointers.

// Insert at position: Insert new node after the n-th node (n starts from 0)
int dinsert_at_position(DNode** head, int n, int val) {
    if (n < 0) return 0;
    if (n == 0) {         // Equivalent to head insertion
        dinsert_at_head(head, val);
        return 1;
    }
    DNode* current = *head;
    for (int i = 0; i < n - 1; i++) {  // Find the (n-1)-th node
        if (current == NULL) return 0;
        current = current->next;
    }
    if (current == NULL) return 0;     // List length less than n
    DNode* new_node = create_dnode(val); // Create new node
    new_node->next = current->next;    // New node's next points to original n-th node
    new_node->prev = current;          // New node's prev points to (n-1)-th node
    if (current->next != NULL) {       // Original n-th node is not tail
        current->next->prev = new_node;  // Original n-th node's prev points to new node
    }
    current->next = new_node;          // (n-1)-th node's next points to new node
    return 1;
}

Delete Node

Deletion requires updating both predecessor and successor pointers, supporting deletion by value and deletion by position.

(1) Delete by Value

Find target node, update predecessor and successor, free memory.

// Delete by value: Delete first node with value val
int ddelete_by_value(DNode** head, int val) {
    if (*head == NULL) return 0;
    DNode* current = *head;
    while (current != NULL) {
        if (current->data == val) {
            if (current->prev == NULL) {  // Target is head node
                *head = current->next;
                if (*head != NULL) {
                    (*head)->prev = NULL;  // New head's prev set to NULL
                }
            } else {
                current->prev->next = current->next;  // Predecessor's next points to target's next
            }
            if (current->next != NULL) {  // Target is not tail
                current->next->prev = current->prev;  // Successor's prev points to target's prev
            }
            free(current);  // Free memory
            return 1;
        }
        current = current->next;
    }
    return 0;  // Target not found
}
(2) Delete by Position

Find the n-th node, update predecessor and successor, free memory.

// Delete by position: Delete the n-th node (n starts from 0)
int ddelete_by_position(DNode** head, int n) {
    if (n < 0 || *head == NULL) return 0;
    if (n == 0) {  // Delete head node
        DNode* temp = *head;
        *head = (*head)->next;
        if (*head != NULL) {
            (*head)->prev = NULL;  // New head's prev set to NULL
        }
        free(temp);
        return 1;
    }
    DNode* current = *head;
    for (int i = 0; i < n; i++) {  // Find the n-th node
        if (current == NULL) return 0;
        current = current->next;
    }
    if (current == NULL) return 0;  // List length less than n
    if (current->prev != NULL) {    // Target is not head
        current->prev->next = current->next;  // Predecessor's next points to target's next
    }
    if (current->next != NULL) {    // Target is not tail
        current->next->prev = current->prev;  // Successor's prev points to target's prev
    }
    free(current);  // Free memory
    return 1;
}

Traverse List

Doubly linked list supports forward traversal (head to tail) and backward traversal (tail to head).

// Forward traversal (head to tail)
void dtraverse_forward(DNode* head) {
    DNode* current = head;
    while (current != NULL) {
        printf("%d <-> ", current->data);
        current = current->next;
    }
    printf("NULL\n");
}

// Backward traversal (tail to head)
void dtraverse_backward(DNode* tail) {
    DNode* current = tail;
    while (current != NULL) {
        printf("%d <-> ", current->data);
        current = current->prev;
    }
    printf("NULL\n");
}

Simple Doubly Linked List Implementation

Below is a simple doubly linked list implementation including creation, insertion, and traversal:

#include <stdio.h>
#include <stdlib.h>

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

// Create new node
Node* createNode(int data) {
    Node* newNode = (Node*)malloc(sizeof(Node));
    if (newNode == NULL) {
        printf("Memory allocation failed!\n");
        exit(1);
    }
    newNode->data = data;
    newNode->next = NULL;
    newNode->prev = NULL;
    return newNode;
}

// Insert node at the end of the list
void insertAtEnd(Node** head, int data) {
    Node* newNode = createNode(data);
    if (*head == NULL) {
        *head = newNode;
        return;
    }
    Node* last = *head;
    while (last->next != NULL) {
        last = last->next;
    }
    last->next = newNode;
    newNode->prev = last;
}

// Print the list
void printList(Node* head) {
    Node* temp = head;
    while (temp != NULL) {
        printf("%d <-> ", temp->data);
        temp = temp->next;
    }
    printf("NULL\n");
}

int main() {
    Node* head = NULL;

    insertAtEnd(&head, 10);
    insertAtEnd(&head, 20);
    insertAtEnd(&head, 30);

    printList(head);

    return 0;
}

Notes for Doubly Linked List

  • Bidirectional Pointer Update: Update both prev and next during insertion/deletion to avoid broken links.
  • Tail Pointer Maintenance: Maintain a separate tail pointer (tail) for frequent tail operations to avoid traversal.
  • Memory Leak: Always free memory after deletion, especially with bidirectional pointers.

Circular Linked List

A circular linked list is a special form of linked list where the last node’s pointer does not point to NULL, but to the first node, forming a closed loop. This structure allows traversal of the entire list from any node until returning to the starting point.

Node Structure of a Circular Linked List

The node structure of a circular linked list is similar to singly or doubly linked lists, except the last node’s next points to the head.

For a singly circular linked list, the node structure is:

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

For a doubly circular linked list, the node structure is:

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

Operations on Circular Linked List

Operations are similar to regular linked lists but differ slightly due to the loop nature, especially in traversal and insertion/deletion.

1. Create circular list: Create a node and make its next point to itself, forming a loop. 2. Insert node:

  • Insert at head: New node’s next points to current head, update current head’s prev (if doubly), update head to new node.
  • Insert at tail: Find last node, update its next to new node, new node’s next to head.
  • Insert in middle: Find position, update next and prev of adjacent nodes (if doubly).

3. Delete node: Update predecessor’s next and successor’s prev (if doubly), then free memory. 4. Traverse list: Start from head, visit nodes until back to head. 5. Free list: Release memory of all nodes.

Create Node

Similar to singly linked list, but adjust next to point to head during insertion.

// Create new circular linked list node (with value val)
CircularNode* create_circular_node(int val) {
    CircularNode* new_node = (CircularNode*)malloc(sizeof(CircularNode));
    if (new_node == NULL) {
        perror("malloc failed");
        exit(EXIT_FAILURE);
    }
    new_node->data = val;
    new_node->next = NULL;  // Initially no next node (adjusted on insert)
    return new_node;
}

Insert Node

Insertion supports head insertion and tail insertion, ensuring tail’s next points to head.

(1) Head Insertion

Insert new node before head, tail’s next points to new node.

// Head insertion: Insert new node at the head of the circular list
void circ_insert_at_head(CircularNode** head, int val) {
    CircularNode* new_node = create_circular_node(val);
    if (*head == NULL) {                // Empty list, node loops to itself
        new_node->next = new_node;
        *head = new_node;
        return;
    }
    CircularNode* tail = *head;
    while (tail->next != *head) {       // Find tail node
        tail = tail->next;
    }
    new_node->next = *head;             // New node's next points to original head
    tail->next = new_node;              // Tail's next points to new node
    *head = new_node;                   // Update head to new node
}
(2) Tail Insertion

Insert new node after tail, tail’s next points to new node, new node becomes new tail.

// Tail insertion: Insert new node at the tail of the circular list
void circ_insert_at_tail(CircularNode** head, int val) {
    CircularNode* new_node = create_circular_node(val);
    if (*head == NULL) {                // Empty list, node loops to itself
        new_node->next = new_node;
        *head = new_node;
        return;
    }
    CircularNode* tail = *head;
    while (tail->next != *head) {       // Find tail node
        tail = tail->next;
    }
    tail->next = new_node;              // Tail's next points to new node
    new_node->next = *head;             // New node's next points to head (forms loop)
}

Delete Node

Deletion requires finding the predecessor of the target, adjusting pointers, and ensuring tail’s next points to head.

// Delete by value: Delete first node with value val
int circ_delete_by_value(CircularNode** head, int val) {
    if (*head == NULL) return 0;
    CircularNode* current = *head;
    CircularNode* prev = NULL;
    do {                                // Loop traversal (at least check head)
        if (current->data == val) {
            if (prev == NULL) {         // Target is head node
                if (current->next == *head) {  // Only one node
                    *head = NULL;
                } else {
                    CircularNode* tail = *head;
                    while (tail->next != *head) {  // Find tail
                        tail = tail->next;
                    }
                    tail->next = current->next;  // Tail's next points to new head
                    *head = current->next;       // Update head to new head
                }
            } else {
                prev->next = current->next;  // Predecessor's next points to target's next
                if (current->next == *head) {  // Target is tail
                    *head = current->next;     // New tail's next points to head (already handled by prev->next)
                }
            }
            free(current);  // Free memory
            return 1;
        }
        prev = current;
        current = current->next;
    } while (current != *head);  // Loop until back to head
    return 0;  // Target not found
}

Traverse List

Traversal requires a stop condition (e.g., traverse n times or return to head).

// Traverse circular list (from head, visit all nodes)
void circ_traverse(CircularNode* head) {
    if (head == NULL) return;
    CircularNode* current = head;
    do {
        printf("%d <-> ", current->data);
        current = current->next;
    } while (current != head);  // Stop when back to head
    printf("HEAD\n");           // Mark head node
}

Simple Singly Circular Linked List Implementation

Below is a simple singly circular linked list implementation including creation, insertion, and traversal:

#include <stdio.h>
#include <stdlib.h>

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

// Create new node
Node* createNode(int data) {
    Node* newNode = (Node*)malloc(sizeof(Node));
    if (newNode == NULL) {
        printf("Memory allocation failed!\n");
        exit(1);
    }
    newNode->data = data;
    newNode->next = NULL;
    return newNode;
}

// Insert node at the end of the list
void insertAtEnd(Node** head, int data) {
    Node* newNode = createNode(data);
    if (*head == NULL) {
        *head = newNode;
        newNode->next = *head;
    } else {
        Node* last = *head;
        while (last->next != *head) {
            last = last->next;
        }
        last->next = newNode;
        newNode->next = *head;
    }
}

// Print the list
void printList(Node* head) {
    Node* temp = head;
    do {
        printf("%d -> ", temp->data);
        temp = temp->next;
    } while (temp != head);
    printf("NULL\n");
}

int main() {
    Node* head = NULL;

    insertAtEnd(&head, 10);
    insertAtEnd(&head, 20);
    insertAtEnd(&head, 30);

    printList(head);

    return 0;
}

Notes for Circular Linked List

  • Loop Termination Condition: Clearly define stop condition during traversal/operation (e.g., return to head) to avoid infinite loops.
  • Tail Pointer Maintenance: Maintain a separate tail pointer (tail) for frequent tail operations to avoid traversal.
  • Single Node Handling: When only one node exists, its next points to itself; special handling needed on deletion.

Comparison and Selection Suggestions for Linked Lists

Comparison of Three Linked List Types

OperationTime Complexity (Singly)Time Complexity (Doubly)Time Complexity (Circular)
Head InsertionO(1)O(1)O(1)
Tail InsertionO(n)O(n) (no tail pointer)O(n) (no tail pointer)
Insert at PositionO(n)O(n)O(n)
Delete by ValueO(n)O(n)O(n)
Delete by PositionO(n)O(n)O(n)
Forward TraversalO(n)O(n)O(n)
Backward TraversalNot supportedO(n)Not supported (requires reversal)

Selection Suggestions

  • Singly Linked List: Low memory usage, suitable for sequential access and tail-dominant insertion (e.g., log recording).
  • Doubly Linked List: Supports bidirectional traversal, more efficient insertion/deletion, suitable for frequent middle operations (e.g., editor buffer).
  • Circular Linked List: Suitable for ring-shaped data structures (e.g., round-robin scheduling, circular buffer).

Practical Project: Student Grade Management System

Requirements Description

Implement a student grade management system that supports:

  • Adding student information (ID, name, score).
  • Searching student by ID.
  • Deleting student by ID.
  • Traversing all student information.

Implementation Code (Doubly Linked List)

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

// Define student struct (doubly linked list node)
typedef struct Student {
    char id[20];      // Student ID
    char name[50];    // Name
    float score;      // Score
    struct Student* prev;  // Predecessor pointer
    struct Student* next;  // Successor pointer
} Student;

// Create new student node
Student* create_student(const char* id, const char* name, float score) {
    Student* new_student = (Student*)malloc(sizeof(Student));
    if (new_student == NULL) {
        perror("malloc failed");
        exit(EXIT_FAILURE);
    }
    strcpy(new_student->id, id);
    strcpy(new_student->name, name);
    new_student->score = score;
    new_student->prev = NULL;
    new_student->next = NULL;
    return new_student;
}

// Add student using head insertion
void add_student_head(Student** head, Student* new_student) {
    if (*head == NULL) {
        *head = new_student;
        return;
    }
    new_student->next = *head;
    (*head)->prev = new_student;
    *head = new_student;
}

// Add student using tail insertion
void add_student_tail(Student** head, Student* new_student) {
    if (*head == NULL) {
        *head = new_student;
        return;
    }
    Student* current = *head;
    while (current->next != NULL) {
        current = current->next;
    }
    current->next = new_student;
    new_student->prev = current;
}

// Search student by ID
Student* find_student(Student* head, const char* id) {
    Student* current = head;
    while (current != NULL) {
        if (strcmp(current->id, id) == 0) {
            return current;
        }
        current = current->next;
    }
    return NULL;
}

// Delete student by ID
int delete_student(Student** head, const char* id) {
    if (*head == NULL) return 0;
    Student* current = *head;
    while (current != NULL) {
        if (strcmp(current->id, id) == 0) {
            if (current->prev == NULL) {  // Head node
                *head = current->next;
                if (*head != NULL) {
                    (*head)->prev = NULL;
                }
            } else {
                current->prev->next = current->next;
            }
            if (current->next != NULL) {
                current->next->prev = current->prev;
            }
            free(current);
            return 1;
        }
        current = current->next;
    }
    return 0;
}

// Traverse all students
void traverse_students(Student* head) {
    Student* current = head;
    while (current != NULL) {
        printf("ID: %s, Name: %s, Score: %.2f\n", 
               current->id, current->name, current->score);
        current = current->next;
    }
}

int main() {
    Student* head = NULL;

    // Add students (tail insertion)
    Student* s1 = create_student("001", "Zhang San", 85.5);
    add_student_tail(&head, s1);
    Student* s2 = create_student("002", "Li Si", 92.0);
    add_student_tail(&head, s2);
    Student* s3 = create_student("003", "Wang Wu", 78.5);
    add_student_tail(&head, s3);

    printf("All student information:\n");
    traverse_students(head);

    // Search student (ID 002)
    Student* found = find_student(head, "002");
    if (found) {
        printf("\nFound student: ID %s, Name %s, Score %.2f\n", 
               found->id, found->name, found->score);
    }

    // Delete student (ID 002)
    if (delete_student(&head, "002")) {
        printf("\nStudent information after deleting ID 002:\n");
        traverse_students(head);
    }

    return 0;
}

Compile and Run:

gcc -o student_management student_management.c
./student_management

Output Result:

All student information:
ID: 001, Name: Zhang San, Score: 85.50
ID: 002, Name: Li Si, Score: 92.00
ID: 003, Name: Wang Wu, Score: 78.50

Found student: ID 002, Name Li Si, Score 92.00

Student information after deleting ID 002:
ID: 001, Name: Zhang San, Score: 85.50
ID: 003, Name: Wang Wu, Score: 78.50
Course: Mastering C Programming From Basics to Advanced Techniques
Share your love

Trending now

Exploring Web 3D Core Technologies Development
Assembly Language Programming From Low-Level Logic to System Kernel
WebRTC Advanced Guide：Media, Transport & Architecture
WebSocket Deep Guide：Building High-Performance Realtime Systems