A doubly linked list is a data structure where each node is connected to the next and the previous nodes through two pointers. Each node contains two pointers: one pointing to the previous node and another pointing to the next node. Doubly linked lists with a head node are common in practical applications. This article will provide a detailed explanation of how to implement a doubly linked list, along with a complete example in C.
一. Types of Linked Lists
Linked lists can be structured in various ways, leading to 8 possible combinations (2 x 2 x 2) of different types:
1. Singly or Doubly Linked
Singly Linked List:
Each node contains a pointer to the next node.
Traversal is one-way (from head to tail).
Insertion and deletion are simple, but nodes need to be found starting from the head.
Doubly Linked List:
Each node contains two pointers: one pointing to the next node and one pointing to the previous node.
Can be traversed both ways (head to tail and tail to head).
Insertion and deletion are more flexible but require more memory for the additional pointers.
2. With or Without Head Node
With Head Node:
The list has an additional head node that does not store actual data but serves as the starting point for the list.
Operations like insertion and deletion are simpler, as the head node simplifies boundary conditions.
Without Head Node:
The list starts directly from the first data node, with no extra head node.
Special handling is required for empty lists and boundary conditions.
3. Circular or Non-Circular
Circular Linked List:
The tail node points to the head node, creating a circular structure.
Traversal can start from any node, avoiding the "end" problem.
Non-Circular Linked List:
The tail node points to
NULL, marking the end of the list.During traversal, checks are needed to see if the end has been reached.
Although there are many types of linked list structures, the two most commonly used in practice are:
Singly Linked Non-Circular List: Simple structure, generally used as part of other data structures like hash buckets or adjacency lists in graphs. It is also a common type in interviews and exams.
Doubly Circular Linked List with Head Node: More complex structure, commonly used for storing data independently. This type of list is frequently used in practical applications, as it simplifies operations despite its more complex structure.
二. Concept and Basic Structure of a Doubly Linked List
2.1 Concept
A doubly linked list is a variation of a linked list where each node contains three parts:
Data to be stored.
A pointer to the previous node (
prev).A pointer to the next node (
next).
A doubly linked list with a head node includes a special node called the head node, which does not store valid data and serves only as the starting auxiliary node of the list. The prev pointer of the head node points to itself, and its next pointer points to the first valid node in the list.
2.2 Basic Structure
The basic structure of a doubly linked list is defined as:
typedef struct ListNode
{
DataType data; // Data field
struct ListNode* prev; // Pointer to the previous node
struct ListNode* next; // Pointer to the next node
} LN;
三. Common Operations on a Doubly Linked List
Creating a Node
// Create a new node
LN* ListBuyNode(DataType x)
{
LN* node = (LN*)malloc(sizeof(LN));
if (node == NULL)
{
perror("malloc fail!");
exit(1);
}
node->data = x;
node->prev = node->next = node; // Both pointers point to itself, forming a circular list
return node;
}Initializing the List
// Initialize the list
void ListInit(LN** pphead)
{
*pphead = ListBuyNode(-1); // Create the head node with a value of -1 (unused)
}Insert at the Head
// Insert a node at the front
void ListPushFront(LN* phead, DataType x)
{
assert(phead);
LN* newnode = ListBuyNode(x);
newnode->next = phead->next; // New node's next points to the head's next node
newnode->prev = phead; // New node's prev points to the head
phead->next->prev = newnode; // The previous node's prev points to the new node
phead->next = newnode; // The head's next points to the new node
}
Insert at the Tail
// Insert a node at the end
void ListPushBack(LN* phead, DataType x)
{
assert(phead);
LN* newnode = ListBuyNode(x);
newnode->prev = phead->prev; // New node's prev points to the old tail node
newnode->next = phead; // New node's next points to the head
phead->prev->next = newnode; // The old tail's next points to the new node
phead->prev = newnode; // The head's prev points to the new node
}
Delete from the Head
// Delete the node at the front
void ListPopFront(LN* phead)
{
assert(phead && phead->next != phead); // Ensure the list is not empty
LN* del = phead->next;
del->next->prev = phead; // The next node's prev points to the head
phead->next = del->next; // The head's next points to the deleted node's next
free(del); // Free the memory of the deleted node
del = NULL;
}
Delete from the Tail
// Delete the node at the end
void ListPopBack(LN* phead)
{
assert(phead && phead->next != phead); // Ensure the list is not empty
LN* del = phead->prev;
del->prev->next = phead; // The previous node's next points to the head
phead->prev = del->prev; // The head's prev points to the deleted node's prev
free(del); // Free the memory of the deleted node
del = NULL;
}
Print the List
// Print the list
void ListPrint(LN* phead)
{
LN* pcur = phead->next;
while (pcur != phead)
{
printf("%d->", pcur->data); // Print the current node's data
pcur = pcur->next;
}
printf("NULL\n"); // Print the end of the list
}
Find a Node
// Find a node in the list
LN* ListFind(LN* phead, DataType x)
{
LN* pcur = phead->next;
while (pcur != phead)
{
if (pcur->data == x)
{
return pcur; // Return the node if found
}
pcur = pcur->next;
}
return NULL; // Return NULL if the node is not found
}Insert a Node at a Position
// Insert a node after a specified position
void ListInsert(LN* pos, DataType x)
{
assert(pos);
LN* newnode = ListBuyNode(x);
newnode->next = pos->next; // New node's next points to pos's next
newnode->prev = pos; // New node's prev points to pos
pos->next->prev = newnode; // pos's next's prev points to the new node
pos->next = newnode; // pos's next points to the new node
}
Delete a Node at a Position
// Delete a node at a specified position
void ListErase(LN* pos)
{
assert(pos);
pos->next->prev = pos->prev; // The next node's prev points to the previous node
pos->prev->next = pos->next; // The previous node's next points to the next node
free(pos); // Free the memory of the node
pos = NULL;
}
Destroy the List
// Destroy the list
void ListDestroy(LN* phead)
{
assert(phead);
LN* pcur = phead->next;
while (pcur != phead)
{
LN* next = pcur->next;
free(pcur); // Free the current node's memory
pcur = next;
}
free(phead); // Free the head node's memory
phead = NULL;
}
Note: In the ListErase and ListDestroy functions, the parameter phead should ideally beaffected if passed by a single pointer level, but for consistency, the function interfaces use a single pointer. As a workaround, after calling these functions, set the actual parameter to NULL manually.
四. Complete Code
1. List.h
This section contains the definition of the ordered list structure and function declarations.
#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
typedef int DataType;
typedef struct ListNode
{
DataType data; // Data field
struct ListNode* prev; // Pointer to the previous node
struct ListNode* next; // Pointer to the next node
} LN;
// Function Declarations:
void ListInit(LN** pphead); // Initialize the list
void ListPushBack(LN* phead, DataType x); // Insert node at the end
void ListPushFront(LN* phead, DataType x); // Insert node at the front
void ListPrint(LN* phead); // Print the list
void ListPopBack(LN* phead); // Remove node from the end
void ListPopFront(LN* phead); // Remove node from the front
LN* ListFind(LN* phead, DataType x); // Find a node
void ListInsert(LN* pos, DataType x); // Insert node after the specified position
void ListErase(LN* pos); // Delete a node
void ListDestroy(LN* phead); // Destroy the list2. List.c
This section contains the implementation of the functions.
#define _CRT_SECURE_NO_WARNINGS
#include"List.h"
// Create a new node
LN* ListBuyNode(DataType x)
{
LN* node = (LN*)malloc(sizeof(LN));
if (node == NULL)
{
perror("malloc fail!");
exit(1);
}
node->data = x;
node->prev = node->next = node; // Both pointers point to itself, forming a circular list
return node;
}
// Initialize the list
void ListInit(LN** pphead)
{
*pphead = ListBuyNode(-1); // Create the head node with value -1 (not used)
}
// Insert node at the end
void ListPushBack(LN* phead, DataType x)
{
assert(phead);
LN* newnode = ListBuyNode(x);
newnode->prev = phead->prev; // New node's previous pointer points to the original tail
newnode->next = phead; // New node's next pointer points to the head node
phead->prev->next = newnode; // Original tail's next points to new node
phead->prev = newnode; // Head node's previous points to new node
}
// Insert node at the front
void ListPushFront(LN* phead, DataType x)
{
assert(phead);
LN* newnode = ListBuyNode(x);
newnode->next = phead->next; // New node's next points to the head's next node
newnode->prev = phead; // New node's previous points to the head
phead->next->prev = newnode; // Head's next node's previous points to the new node
phead->next = newnode; // Head node's next points to new node
}
// Remove node from the end
void ListPopBack(LN* phead)
{
assert(phead && phead->next != phead); // Ensure the list is not empty
LN* del = phead->prev;
del->prev->next = phead; // Previous node's next points to the head node
phead->prev = del->prev; // Head node's previous points to the deleted node's previous
free(del); // Free the memory of the deleted node
del = NULL;
}
// Remove node from the front
void ListPopFront(LN* phead)
{
assert(phead && phead->next != phead); // Ensure the list is not empty
LN* del = phead->next;
del->next->prev = phead; // Deleted node's next node's previous points to head
phead->next = del->next; // Head node's next points to the deleted node's next
free(del); // Free the memory of the deleted node
del = NULL;
}
// Print the list
void ListPrint(LN* phead)
{
LN* pcur = phead->next;
while (pcur != phead)
{
printf("%d->", pcur->data); // Print the data of the current node
pcur = pcur->next;
}
printf("NULL\n"); // Print the end marker of the list
}
// Find a node in the list
LN* ListFind(LN* phead, DataType x)
{
LN* pcur = phead->next;
while (pcur != phead)
{
if (pcur->data == x)
{
return pcur; // Return the node if a match is found
}
pcur = pcur->next;
}
return NULL; // Return NULL if no match is found
}
// Insert a node after the specified position
void ListInsert(LN* pos, DataType x)
{
assert(pos);
LN* newnode = ListBuyNode(x);
newnode->next = pos->next; // New node's next points to pos's next node
newnode->prev = pos; // New node's previous points to pos
pos->next->prev = newnode; // pos's next node's previous points to the new node
pos->next = newnode; // pos's next points to new node
}
// Delete a node at the specified position
void ListErase(LN* pos)
{
assert(pos);
pos->next->prev = pos->prev; // Next node's previous points to the deleted node's previous
pos->prev->next = pos->next; // Previous node's next points to the deleted node's next
free(pos); // Free the memory of the deleted node
pos = NULL;
}
// Destroy the list
void ListDestroy(LN* phead)
{
assert(phead);
LN* pcur = phead->next;
while (pcur != phead)
{
LN* next = pcur->next;
free(pcur); // Free the memory of the current node
pcur = next;
}
free(phead); // Free the memory of the head node
phead = NULL;
}3. test.c
Test, calling the functions.
#define _CRT_SECURE_NO_WARNINGS
#include"List.h"
void test01()
{
LN* plist = NULL;
ListInit(&plist);
// ListPushFront(plist, 1);
ListPushFront(plist, 2);
ListPushFront(plist, 3);
ListPushFront(plist, 4);
LN* find = ListFind(plist, 3);
ListInsert(find, 99);
ListErase(find);
find = NULL;
ListPrint(plist);
ListDestroy(plist);
plist = NULL;
}
int main()
{
test01();
return 0;
}6. Conclusion
A doubly linked list with a head node offers flexibility when inserting and deleting nodes. The presence of the head node simplifies boundary conditions and reduces special handling for empty lists or boundary cases. With the implementation and example code provided, you should be able to master basic operations on doubly linked lists and apply them in practical programming tasks.
Hope this blog post is helpful!
