Doubly Linked List C Code with Examples
A doubly linked list is a type of data structure that is commonly used in computer programming. It is a series of nodes that are connected to each other through two links, one that points to the previous node and another that points to the next node. In this article, we will discuss the implementation of a doubly linked list in C programming language with examples.
Creating a Doubly Linked List in C
The first step in creating a doubly linked list in C is to define the structure of the node. Each node in the list has three fields, one that holds the data and two that hold the pointers to the previous and next node respectively. The following code snippet shows how to define the structure of a doubly linked list node.
struct Node {
int data;
struct Node* next;
struct Node* prev;
};
After defining the structure of the node, we can create the doubly linked list using pointers to the first and last nodes. The following code snippet shows how to create an empty doubly linked list.
struct Node* head = NULL;
struct Node* tail = NULL;
Inserting a Node in a Doubly Linked List
To insert a node in a doubly linked list, we need to follow the following steps:
- Dynamically allocate a new node.
- Assign the data to the new node.
- Assign the next and prev pointers of the new node.
- Assign the next and prev pointers of the adjacent nodes.
The following code snippet shows how to insert a node at the beginning of the doubly linked list.
void insertFirst(int data) {
struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
newNode->data = data;
newNode->prev = NULL;
newNode->next = head;
if (head != NULL) {
head->prev = newNode;
}
head = newNode;
if (tail == NULL) {
tail = newNode;
}
}
The function takes the data to be inserted as an argument. It dynamically allocates a new node and assigns the data to it. It then assigns the next pointer of the new node to the head pointer and the prev pointer to NULL. If the head is not NULL, it assigns the prev pointer of the head node to the new node. Finally, it updates the head pointer to the new node.
Similarly, we can insert a node at the end of the doubly linked list using the following code snippet.
void insertLast(int data) {
struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
newNode->data = data;
newNode->next = NULL;
if (tail != NULL) {
tail->next = newNode;
newNode->prev = tail;
tail = newNode;
} else {
head = newNode;
tail = newNode;
newNode->prev = NULL;
}
}
The function takes the data to be inserted as an argument. It dynamically allocates a new node and assigns the data to it. If the tail is not NULL, it assigns the next pointer of the tail node to the new node and the prev pointer of the new node to the tail node. Finally, it updates the tail pointer to the new node. If the tail is NULL, it means that the doubly linked list is empty. In this case, it assigns the head and tail pointers to the new node and assigns NULL to the prev pointer of the new node.
Deleting a Node from a Doubly Linked List
To delete a node from a doubly linked list, we need to follow the following steps:
- Find the node to be deleted.
- Update the next and prev pointers of the adjacent nodes.
The following code snippet shows how to delete a node from the doubly linked list.
void deleteNode(struct Node* node) {
if (node == head) {
head = node->next;
} else if (node == tail) {
tail = node->prev;
}
if (node->prev != NULL) {
node->prev->next = node->next;
}
if (node->next != NULL) {
node->next->prev = node->prev;
}
free(node);
}
The function takes the node to be deleted as an argument. It checks if the node to be deleted is the head or the tail node and updates the head and tail pointers accordingly. It then updates the next and prev pointers of the adjacent nodes to remove the node from the list. Finally, it frees the memory allocated to the node.
Traversing a Doubly Linked List
To traverse a doubly linked list, we need to follow the following steps:
- Start at the head node.
- Print the data of the node.
- Move to the next node.
The following code snippet shows how to traverse a doubly linked list.
void printList() {
struct Node* current = head;
while (current != NULL) {
printf("%d ", current->data);
current = current->next;
}
printf("
");
}
The function starts at the head node and prints the data of the node. It then moves to the next node and repeats the process until the end of the list is reached.
Conclusion
In this article, we discussed how to implement a doubly linked list in C language with examples. We learned how to create an empty doubly linked list, insert a node at the beginning and end of the list, delete a node from the list, and traverse the list. The implementation of a doubly linked list is useful in many applications that require efficient memory management and data access.
I'd be happy to provide more information on the previously discussed topics.
Creating a Doubly Linked List in C
When creating a doubly linked list in C, it's important to keep track of both the head and the tail pointers. The head pointer always points to the first node in the list, while the tail pointer always points to the last node in the list. This makes it easier to add and remove nodes from both the beginning and end of the list because the tail pointer can be used to quickly access the last node.
Another important consideration when creating a doubly linked list in C is memory allocation. Each node in the list must be dynamically allocated using the malloc() function, and care must be taken to properly free the memory when the nodes are no longer needed.
Inserting a Node in a Doubly Linked List
In addition to inserting a node at the beginning or end of a doubly linked list, it's also possible to insert a node in the middle of the list. To do this, you need to traverse the list until you find the desired position, adjust the pointers of the previous and next nodes to point to the new node, and adjust the pointers of the new node to point to the previous and next nodes.
Deleting a Node from a Doubly Linked List
Just like inserting a node, deleting a node can be done from anywhere in the list. To delete a node, you need to adjust the pointers of the previous and next nodes to point to each other, and then free the memory allocated to the deleted node.
Traversing a Doubly Linked List
In addition to printing the data of each node, it's also possible to traverse a doubly linked list in reverse order by starting at the tail pointer and moving backwards through the list. This can be useful in situations where you need to process the data in reverse order, such as when printing a file in reverse order.
In general, doubly linked lists are useful in situations where you need to efficiently add and remove nodes from both the beginning and end of the list, or when you need to traverse the list in both forward and reverse order. However, they are not always the best choice for all situations – for example, if you only need to add and remove nodes from the end of the list, a singly linked list may be more appropriate.
Popular questions
-
What are the advantages of a doubly linked list over a singly linked list?
A doubly linked list allows for efficient insertion and removal of nodes from both the beginning and end of the list since each node has a pointer to both the previous and next nodes. Additionally, doubly linked lists support traversal in both forward and reverse directions. -
How is a doubly linked list initialized in C?
To initialize a doubly linked list in C, you must define the structure of the node with three fields – data, next pointer, and previous pointer. You also need to declare two pointers – one for the head and one for the tail. The head and tail pointers must be set to NULL to indicate an empty list. -
How is a node inserted at the beginning of a doubly linked list in C?
To insert a node at the beginning of a doubly linked list in C, you need to dynamically allocate a new node, assign the data to the new node, and adjust the pointers of the new node and the head node. Here's some example code:
void insertAtBeginning(int data) {
struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
newNode->data = data;
newNode->next = head;
newNode->prev = NULL;
if (head != NULL) {
head->prev = newNode;
}
head = newNode;
if (tail == NULL) {
tail = newNode;
}
}
- How is a node deleted from a doubly linked list in C?
To delete a node from a doubly linked list in C, you must adjust the pointers of the previous and next nodes to bypass the node to be deleted. Here's some example code:
void deleteNode(struct Node* node) {
if (node == head) {
head = node->next;
} else if (node == tail) {
tail = node->prev;
}
if (node->prev != NULL) {
node->prev->next = node->next;
}
if (node->next != NULL) {
node->next->prev = node->prev;
}
free(node);
}
- How is a doubly linked list traversed in C?
To traverse a doubly linked list in C, you can start at the head node and move sequentially through each node until the end of the list is reached. Here's some example code:
void traverseList() {
struct Node* currentNode = head;
while (currentNode != NULL) {
printf("%d ", currentNode->data);
currentNode = currentNode->next;
}
printf("
");
}
Tag
Listetics.
