How to Create a Doubly-Linked List in C Programming
Programmers use linked lists as linearly traversable data structures. This means that the programmer can start from the beginning of the list (called the head) and move forward through the list one item at a time. This method of data storage also allows the programmer to efficiently add data to the list, offering a more versatile alternative to certain other data structures such as dynamic arrays. This example shows how to construct a simple doubly-linked list, which allows navigation of the list on two directions (forward and reverse).
Other People Are Reading
Instructions
-
-
1
Create the node structure that will serve as the data type of the linked list. In the text editor, enter the following code:
#include <stdlib.h>
int main{
struct listNode{
int data;
strut listNode *prev;
strut listNode *next;
};
return 0;
}
The "struct listNode" block of code creates a template for the items that will populate the list. This template defines a listNode as containing three elements: a data item (an integer) and pointers to the previous and next items in the list. A pointer is a variable that holds an memory address. Pointers are used to refer to other data structures in deep memory and to dynamically allocate memory during code execution.
-
2
Declare the variables that will organize the list structure. Insert this example code into the text file:
int size;
listNode *head;
listNode *tail;
tail = head;
head = tail;
These two pointers are the beginning and end of the list, respectively. Using these pointers, the programmer knows where the beginning of the list is and where the end is, simply by checking if the current node is the "head" or "tail" pointer. They both refer back to each other in the event of an empty list.
-
-
3
Create an simple algorithm to append items from the linked list. Follow this example code:
void append(int num){
struct listNode *tracer = head;
struct listNode *newNode = (struct listNode*)malloc(sizeof(struct listNode));
newNode->data = num;
if (head == NULL){
head = newNode;
tail = newNode;
newNode->prev = head;
newNode->next = tail;
}
else{
while (tracer->next != tail)
{tracer = tracer->next;}
newNode->prev = tracer;
newNode->next = tail;
tracer->next = node;
tail = node;
}
size++;
}
This code appends a node to the end of the list. It begins by creating a pointer to the head of the list ("tracer"). Then, it creates a pointer to a dynamically allocated block of memory set aside for a newly created listNode (newNode) and sets the data of that node to the integer "num". If the head points to NULL (meaning the list is empty, because the head points to nothing), then, the code inserts the node at the beginning of the list. Otherwise, the "while" loop cycles through the nodes in the list until reaching the last node. When "tracer" points to the last element of the list, the code inserts the node. The final command adds to the "size" integer, keeping track of the elements in the list.
-
4
Create an algorithm to remove and item from the end of the list:
void removeNode(){
if (tail != head){
struct listNode *end = tail;
tail = tail->prev;
free(end);
size--;
}
}
This code creates a pointer ("end") to the last element of the list (the same element "tail" points to). Then, tail is set to point to the element immediately before the last element (the node pointed to by the "prev" pointer of the last element). Finally, the memory used by last node, referred to by "end", is freed up for further use.
-
1
Tips & Warnings
This is only a skeleton of a doubly-linked list. Other functionality, such as ordering of data, insertion into the middle of the list, and removal from the middle of the list, can be added to this basic functionality.
References
- Photo Credit Comstock/Comstock/Getty Images
More Like This
Comments
-
I like the way gives the information of given topic..........
