Chapter 7 Lists
Runhe Huang and Jianhua Ma, Hosei University, Japan ({rhuang,
jianhua}@k.hosei.ac.jp)
Chapter Outline
7.1. Introduction of Nodes, Links, and Linked Lists
7.2. Singly Linked Lists
7.2.1. Singly Linked List Processing: Insertion, Deletion, Finding
7.2.2. Implementing Stacks with Singly Linked Lists
7.2.3. Implementing Queues with Singly Linked Lists
7.2.4. Double-ended Linked Lists
7.3. Doubly Linked Lists
7.3.1. Doubly Linked List Processing: Traversal, Insertion, Deletion
7.3.2. Implementing Deques with Doubly Linked Lists
Exercises
Appendices
Appendix 7.1: The source program in C of Implementation of a Singly Linked List
Appendix 7.2: The source program in C of Implementation of a Doubly Linked List
Appendix 7.3: The file, record.dat
In this chapter, two kinds of linked lists are introduced, i.e., singly linked lists and doubly linked
lists. Through implementations of stacks, queues, and deques with singly linked lists and doubly
linked lists, we study or review other data structures as well. Taking student data as an example, we
provide readers many functions and two complete source programs in C.
7.1 Introduction
In this section, we introduce some basic concepts related to lists so as to make you understand what
is a structure and how to define a structure, what is a node and how to define a node, what is a link
and what is a linked list.
First, let us explain what is a structure.
A structure is a collection of elements each of which can be of different types.
Taking student data as an example and assuming it includes student name, student identity number,
and student height, we can define student data as a structure like below rather than as individual
separated data items.
As we can see that student name has a data type of ©har, student identity number has a data type of
int, and student height has a data type of float. The structure, STUDENT_DATA, is a collection of
three different types of data elements. Now, we can use STUDENT_DATA
as a variable type to
define variables. studentA and *pstudent_data are variables that are of STUDENT_DATA type.
It is possible to create arrays of structures since a structure is a data object. An array of a structure is
declared by preceding the array name with the structure typedef name.
Indexing into an array is not as efficient as using a pointer to an array by assigning the pointer to the
base of the array as follows.
As we can see that one of the disadvantages of using an array of structures is that the size of the
array has to be fixed. When the number of structures to be used is somehow uncertainty or may be
changing dynamically during runtime, there is a difficulty to allocate memory to an array. The
solution to this problem is to use a linked list.
What is a linked list?
A linked list is a chain of self-referential structures that are linked one to another.
Taking the same example of student data, we can define the structure of student data in a linked list
as follows.
typedef struct s_data{
char student_name[14];
int student_ID;
float student_height;
}STUDENT_DATA;
STUDENT_DATA studentA, *pstudent_data;
STUDENT_DATA student[36];
STUDENT_DATA student[36], *pstudent_data;
pstudent_data = (STUDENT_DATA *) malloc(sizeof (STUDENT_DATA));
pstudent_data = &student[0]; //base = &student[0];
Where, next is a pointer, is also so called a link or a reference. Since the structure, s_data, contains
the pointer (next) to the instance of itself. It is usually called as a self-referential structure. Different
from an array of structure, a linked list is able to allocate memory for new structures as needed using
the runtime library routine mallloc() and calloc() in C. Obviously, the advantages of a linked list
over an array of structure are that it can grow and shrink in size and provides flexibility of
rearranging the items efficiently.
In a linked list, each structure contains data items and a reference/references to the next
structure/structures in the list. Such structure is called a node. If every node in a linked list has only
one link to the next node and the last node has a null next reference, which indicates the termination
of the list, the linked list is called as a singly linked list as shown in Figure 7.2.
If the last node has a link to the head node instead of a null reference, the linked list is called as a
circular linked list as shown in Figure 7.3.
If every node has two links, one is to the next node and one is to the preceding node in the list. The
linked list is called as a doubly linked list. For a doubly linked list, traversals are in either direction.
The ending node in either direction has a link to null reference as shown in Figure 7.4.
typedef struct s_data{
char student_name[14];
int student_ID;
float student_height;
struct s_data *next;
}STUDENT_DATA;
7.2 Singly Linked Lists
In this session, we discuss basic processing on singly linked lists, which includes creation of a node,
insertion of a node to a list, deletion of a node, and finding a specified node in a linked list, gives
each function and implementation in C and finally provides you a complete source code of an
example in Appendix 7.1. Let us take student data as an example again and define
STUDENT_DATA structure in the file, st_data.h. For implementation convenience, all necessary
global declarations, library files and header files are included in the file, header.h.
To create a singly linked list node, it is in fact to allocate memory for a node structure using malloc()
and return a pointer to this memory area. The link (next) of the node initially points to a null
reference.
typedef struct s_data{
char student_name[14];
int student_ID;
float student_height;
struct s_data *next;
}STUDENT_DATA;
1. #include “header.h”
2. STUDENT_DATA *create_a_node() {
3. STUDENT_DATA *p;
4. p = (STUDENT_DATA *)malloc(sizeof (STUDENT_DATA ));
5. if (p = = NULL) {
6. printf(“create_a_list_of_student_data: failed.¥n”);
7.
exit(1);
8. }
9. p ->next = NULL;
10. return p;
11. }
#incude <stdio.h>
#include <stdlib>
#include <malloc.h>
#include “st_data.h”
static STUDENT_DATA *head;
st_data.h
header.h
Where, line 3 declares p as a STUDENT_DATA structure pointer, line 4 allocates memory to the
node p, line 5-8 checks if the node p is correctly created, line 9 assigns a NULL reference to the link
of the node p, and line 10 returns the pointer p the allocated memory area.
To add a node, it is to insert a node at the end of a singly linked list. That is to say, after creating a
new node, the task is to find the last node and assign the new node to the link (next) of the last node,
thus, the newly added node becomes the last node instead. If the last node is not found then the new
node should be both the first node and the last node of the singly linked list. In such case, the new
node is assigned to the link of the head node. The head node is initially assigned with a null
reference when the singly linked list is still empty (there is no any other nodes except the head node)
or points to the first node when the singly linked list is not empty.
Where, line 4-5 continues searching until it finds the last node, and line 6 assigns the new node to
the link of the last node or to the head node if the singly linked list is empty.
To insert a node after a specified node, it is first to find the specified node and then assign the new
node to the link of the specified node. At the same time, the new node has to be linked to the
succeeding node of the specified node. That is to say, the succeeding node of the specified node is
assigned to the link of the new node. If the specified node is not found, the insertion operation fails
and exits from the insertion function.
1. #include “header.h”
2. STUDENT_DATA *add_a_node(STUDENT_DATA *new) {
3. STUDENT_DATA *p;
4.
for (p = head; p->next != NULL; p = p->next)
5.
;
6.
p ->next = new;
7. }
Where, line 3-6 checks if the parameters for the function are proper, line 7-8 checks if the specified
node is the last node, line 8 calls the function, add_a_node, since the specified node is the last node.
Line 9-12 inserts the new node after the specified node by adding link_a and changing link_b to
link_c as shown in Figure 7.6.
To delete a node, it is to find the proceeding node (for example, node_x) of the node (for example,
node_y) to be deleted, change the link of node_x so that it points to the succeeding node of node_y,
delete the link of node_y, and finally free the memory used by node_y.
1.
#include "header.h"
2.
void insert_a_node_after(STUDENT_DATA *new, STUDENT_DATA *node_x) {
3.
if (new == NULL || node_x == NULL || new == node_x || node_x->next == new ) {
4. printf(“Bad arguments¥n”);
5. return;
6. }
7. if (node_x->next == NULL) /* check if it is the last node */
8. add_a_node(new);
9.
else {
10. new->next = node_x->next; /* add link_a*/
11. node_x->next = new; /* change link_b to link_c*/
12.
}
13. }
Where, line 4 checks if node_y is the first node (the one after head node), line 5 changes the link of
the head node so that it points to the succeeding node of node_y if node_y is the first node, line 7-8
continues to search until it finds the proceeding node, node_x, line 9-11 checks if the proceeding
node exists and terminates the function if it does not exist, otherwise the link of the proceeding node
is changed by deleting link_a and link_b and adding link_c in line 13, and line 16 frees memory
space used by node_y.
To find a node, it is to search for the node based on one of its data fields in the structure of node as a
search key. Let us take student ID as a search key in the student data structure. Searching for node is
to traverse the singly linked list until finding one node whose student ID matches the given argument.
If none of the nodes whose student ID matches the given argument, the function returns null,
otherwise it returns the node found.
Where, line 4 goes through the list, line 5-6 returns found node whose student_ID matches the given
argument id, and line 7 returns null reference if there is no matching node.
1. #include "header.h"
2. void delete_a_node(STUDENT_DATA *node_y) {
3. STUDENT_DATA *p;
4. if (node_y == head->next) /* head is the node proceeding node_y */
5. head->next = node_y->next;
6. else { /* find the node p proceeding node_y */
7. for (p=head; ((p != NULL) &&(p->next != node_y)); p = p->next)
8. ;
9. if (p == NULL){ /* check if node p exists */
10. printf(“Failure: can not find node_y!”);
11. return;
12. }
13. p->next = p->next->next;
/* delete two links (link_a and link_b) and add one link link_c*/
15. }
16. free(node_y);
17. }
1. #include “header.h"
2. STUDENT_DATA *find_a_node(int id){
3. STUDENT_DATA *p;
4. for( p=head; p != NULL; p=p->next )
5. if ( p->student_ID= =id)
6. return p;
7. return NULL;
8. }
To traverse a singly linked list, it is to go through and display data items of each node in the linked
list. Assuming that we would like to print out student data of all students, the function below allows
you to do that.
Where, line 4-6 shows that a node pointer starts from head, advances to the next node in each step,
and prints out three data items of each node until the node pointer points to null reference, which
means reaching the end of the singly linked list.
The complete source program of an example that does the testing of all functions introduced in this
section is provided in Appendix 7.1 at the end of this Chapter. This program reads records in data
file record.dat (that is given in Appendix 7.3) and adds each record one by one to the end of the
singly linked list. You can insert a new record to the list after any node (in the main() function of the
program we inserts a new record after head node but you replace head node by any other node), and
delete any node in the singly linked list (in the main() function of the program we deletes the new
node but you can replace the new node by any other specified node). The program also provides
finding ID and name functions that you can test.
7.2.2 Implementing Stacks with Singly Linked Lists
A stack is an object container of objects (data items) that are inserted and removed according to the
last-in-first-out principle. There are basic five operations on a stack, which are stack initialization,
empty stack check, full stack check, pushing an item onto, and popping an item off. There are also
various implementations of stacks. This section first recalls how to implement a stack with an array
and then moves on to implementing stacks with singly linked lists.
Array implementation of a stack is to use an array to hold stack items and a counter to indicate the
total number of items in the stack. Now let us define array size, item’s data type, and stack structure
in a file, stack.h. Five basic operations on a stack can be defined in the stack ADT interface in a file,
operation.h, as below.
1. #include “header.h"
2. void traverse_list(){
3. STUDENT_DATA *p;
4. for (p = head; p!=NULL; p= p->next){
5. printf("student name = %s , student ID %d, student height %f.¥n",
p->student_name, p->student_ID, student_height);
6. }
7. }
As for the five operations on a stack, stack_initialize() is to initialize the stack to be empty,
stack_empty() is to check if the stack is empty, stack_full() is to check if the stack is full,
stack_push() is to push an item onto the stack, and stack_pop() is to pop an item off the stack. Their
implementations in C are given below.
As we can see that the problem for implementing stacks with arrays is that we have to fix the size of
an array and it is not possible to change the defined size during runtime. Now, let us introduce how
to implement a stack with a singly linked list. Instead of using an array, we can hold the stack items
in each node of a singly linked list in which size of the list can be dynamically changing, either
shrinking or growing, during runtime. One does not need to worry about whether predefined size is
enough or too big. Stack node structure in a singly linked list can be defined as follows in a file,
stack_node.h.
typedef int ITEM_type;
#define MAXSIZE 10
typedef struct stack{
int top;
ITEM_type stack_array[MAXSIZE];
}STACK;
static STACK *stack;
void stack_initialize()
void stack_push(ITEM_type )
ITEM_type stack_pop( )
int stack_empty()
int stack_full()
stack.h
operation.h
void stack_initialize(){
stack->top = 0;
}
int stack_empty(){
return (stack->top <= 0);
}
int stack_full(){
return (stack->top >= MAXSIZE);
}
void stack_push(ITEM_type item){
if (stack_full() != 0)
printf(“the stack is full!”);
else
stack->stack_array[stack->top++] = item;
}
ITEM_type stack_pop(){
if (stack_empty() != 0)
printf(“the stack is empty!”);
else
return stack->stack_array[--stack->top];
}
typedef int ITEM_type;
#define MAXSIZE 10
typedef struct stack_node {
ITEM_type item;
struct stack_node * next;
}STACK_NODE;
static STACK_NODE *head;
Operations on the stack using a singly linked list (we also call it as linked stack) becomes processing
nodes of the list. Pushing a data item onto the stack corresponds to the process of inserting a node as
the first and popping a data item off the stack corresponds to the process of deleting the first node.
Of course, at first, we need to initialize the singly linked list to be an empty list, that is to say, the list
has only head node at beginning. When inserting an item, it is necessary to make a node with the
given item. Both functions of initializing the linked list and making a node are given below. The
functions presented below need to include stack_node.h file by adding #include "stack_node.h".
To push an item onto a linked stack is to create a node with the given item and insert the node at the
front of the linked list. The function, push_a_node(), is given below.
void stack_initialize() {
head = (STACK_NODE *)malloc(sizeof (STACK_NODE));
if (head = = NULL) {
printf(“run out of memory!.¥n”);
exit(1); }
head->next = NULL;
}
STACK_NODE *make_a_node(ITEM_type item) {
STACK_NODE *p;
p = (STACK_NODE *)malloc(sizeof (STACK_NODE));
if (p = = NULL) {
printf(“run out of memory!¥n”);
exit(1); }
p->item = item;
p ->next = NULL;
return p;
}
#include "stack_node.h"
void push_a_node(ITEM_type item){
STACK_NODE *new;
new = make_a_node(item);
if(new == NULL)
pritf(“Failure: push a nonexistent node!”);
else if (head->next == NULL)
head->next = new; /* add link_a*/
else {
new->next = head->next; /* add link_b*/
head->next = new; /* add link_c*/
}
When the linked list is empty, the process of inserting a node is only to add a link (link_a) from the
head node to the new node. When the linked list is not empty, apart from adding a link between the
head node and the new node, it is also necessary to add a link from the new node to its succeeding
node, that is, the previous first node, and to delete the link between the head node and the previous
first node. Figure 7.9 shows the two cases.
To pop an item off a linked stack is to find the first node, output the item contained in the node,
delete the node, and release memory. The process of deleting a node is to add a link from the head
node to the previous second node. Of course, after the deletion, the previous second node becomes
the current first node. When the stack is empty, there is nothing to pop off.
ITEM_type pop_a_node(){
STACK_NODE *first;
ITEM_type item;
if (head->next ==NULL)
printf(“empty stack!”);
else {
first = head->next; /* find the first node */
item = first->item; /* get the item */
head->next = first->next; /* add like_a*/
free(first);
return item;
}
}
7.2.3 Implementing Queues with Singly Linked Lists
This section will discuss how to implement queues with singly linked lists. At first, we will take a
look how a queue is implemented using an array. A queue is a container of objects that are inserted
and removed according to the first-in-first-out principle. Objects can be inserted at any time but
only the object that has been in the queue longest may be removed. Array implementation of a queue
is to use an array to hold the items, a counter to count the number of total items in the queue and two
indices to keep track of the front and the rear of the queue. A data item is inserted from the rear and
removed from the front. The queue structure is defined below in a file, queue.h, and the basic
operations of the queue are defined in the queue ADT interface in a file, operation.h, below.
As for five operations on a queue, queue_initialize() is to initialize the queue to be empty,
queue_empty() is to check if the queue is empty, queue_full() is to check if the queue is full,
enqueue() is to add an item onto the queue, and dequeue() is to delete an item from the queue.
Their implementations use a circular array. A circular array is an array that looks like a circle. The
position around circle is numbered from 0 to MAXSIZE-1. Moving the indices is just the same as
doing modular arithmetic like a circular clock face. When a count is increased to be over
typedef int ITEM_type;
#define MAXSIZE 10
typedef struct queue{
int count;
int head;
int tail;
ITEM_type queue_array[MAXSIZE];
}QUEUE;
Static QUEUE *queue;
void queue_initialize()
void enqueue(ITEM_type )
ITEM_type dequeue( )
int queue_empty()
int queue_full()
queue.h
operation.h
MAXSIZE-1, it starts over again at 0 as shown in Figure 7.11. Then we have,
queue->tail = (queue->tail +1)%MAXSIZE;
queue->head = (queue->head +1)%MAXSIZE;
Such a queue is also called a circular queue from the implementation view of point.
Five functions that operate on a queue using a circular array in C are given below.
void queue_initialize(){
queue->count=0;
queue->head=0;
queue->tail=0;
}
int queue_empty(){
return ( queue->count<= 0);
}
int queue_full(){
return (queue->count >= MAXSIZE);
}
void enqueue(ITEM_type item){
if (queue_full() != 0)
printf(“the queue is full!”);
else {
queue->count++;
queue->tail = (queue->tail + 1)%MAXSIZE;
queue->queue_array[queue->tail] = item;
}
}
ITEM_type dequeue(){
ITEM_type item;
if (queue_empty() != 0)
printf(“the queue is empty!”);
else {
queue->count--;
item = queue->queue->array[queue->head];
queue->head = (queue->head +1)%MAXSIZE;
return item;
}
}
Let us now turn to how to implementing a queue with a singly linked list. Instead of using an array,
we can hold items of the queue in nodes of a singly linked list. It is sometimes called linked queue.
The first thing to do is to define the queue node structure as shown in the file, queue_node.h, below.
Operations on a linked queue become the processing of nodes in a singly linked list, which is very
similar to the operations on a linked stack. The differences are that to enqueue an item to the linked
queue is to add the item to the end of the list as the last node and to dequeue an item is to delete the
first node that contains the item. When adding an item to the linked queue, it is necessary to make a
node with the given item. The function (make_a_node()) below that is mirror to the one given in
Section 7.2.2 makes possible to process an item directly by making a new node with the given item.
To initialize a linked queue is to allocate memory for the head node and the tail node and let both
head and tail nodes point to the NULL reference.
typedef int ITEM_type;
#define MAXSIZE 10
typedef struct queue_node {
ITEM_type item;
struct queue_node * next;
}QUEUE_NODE;
static QUEUE_NODE *head;
static QUEUE_NODE *tail;
QUEUE_NODE *make_a_node(ITEM_type item) {
QUEUE_NODE *p;
p = (QUEUE_NODE *)malloc(sizeof (QUEUE_NODE));
if (p = = NULL) {
printf(“run out of memory!¥n”);
exit(1);
}
p->item = item;
p ->next = NULL;
return p;
}
To enqueue an item to a link queue is to create a node with the given item and insert the
node at the end of the list. There are two possible cases: one is when the linked queue is
empty and another is when the linked queue is not empty. In the former case, after
inserting a new node with the given item, both head and tail nodes point to the new
node while in the later case, the new node is inserted as the current last node. The
previous last node has a linked to the new node and the link of the tail node is also
changed to point the new node. These two cases are illustrated in the figure below.
To delete an item from a link queue is to find the first node, get the item contained in the node,
delete the node, and release memory. If the queue is empty, the function prints out a message like
"empty queue!", otherwise the function continues to process the first node. When the first node is
also the last node, after deletion of the first node, the linked queue becomes empty such that both the
head node and the tail nodes point to a NULL reference. Otherwise the head node points to the
previous second node and the link of the tail node remains the same as shown in the figure below.
#include "queue_node.h"
void queue_initialize() {
head = (QUEUE_NODE *)malloc(sizeof (QUEUE_NODE));
tail = (QUEUE_NODE *)malloc(sizeof (QUEUE_NODE));
if ((head == NULL) || (tail == NULL)) {
printf(“run out of memory!¥n”);
exit(1);
}
head->next = NULL;
tail->next = NULL;
}
#include "queue_node.h"
void enqueue(ITEM_type item){
QUEUE_NODE *new;
new = make_a_node(item);
if(new == NULL)
pritf(“Failure: push a nonexistent node!”);
else if (head->next == NULL)
head->next = new; /* add link_a*/
tail->next = new; /* add link_b*/
}
else {
tail->next->next = new; /* add link_c*/
tail->next = new; /* add link_d*/
}
}
The function, dequeue() that implements deletion of an item from the linked queue is given below.
7.2.4 Double-ended Linked Lists
A double-ended list is similar to a singly linked list discussed earlier, but it has one additional
reference (tail) to the last node as well as to the first node as shown in Figure 7.15. With additional
link to the last node, a double-ended linked list is able to insert a new node directly at the end of the
list without finding the last node by iterating through the entire list as in a single-ended list.
Therefore, it is efficient to insert a new node at the end of the list.
#include "queue_node.h"
ITEM_type dequeue(){
QUEUE_NODE *first;
ITEM_type item;
if (head->next == NULL)
printf(“empty queue!”);
else {
first = head->next; /* find the first node */
item = first->item; /* get the item */
if (first->next == NULL) /*check if first is last node*/
tail->next = NULL; /* add link_b*/
head->next = first->next; /* add link_c or link_a */
free(first);
return item;
}
}
In a single-ended list, inserting a node at the end of the list requires O(n) comparisons. Where, n is
the total number of items in the list since the following loop is used to find the last node.
for (p = head; p->next != NULL; p = p->next)
While in a double-ended list, inserting a node at the end of the list involves changing only one or two
references without requiring any comparisons. It takes O(1) time.
tail->next->next= node;
tail->next= node;
Apart from the insertion of a node at the end of the list is more efficient, other operations on the
double-end linked list are completely same the operations on a single-end linked list. Below we only
present the operation of inserting an item to a double-end linked list.
To insert an item to a double-end linked list becomes quite simple. It can be seen from the source
code of the function below.
void add_node_at_end(STUDENT_DATA *new) {
if(new == NULL)
printf("Failure: push a nonexistent node!");
else if (head -> next == NULL) {
head-> next = new;
tail->next = new;
return;
else{
tail->next->next = new;
tail->next = new;
}
}
7.3 Doubly Linked Lists
7.3.1 Doubly Linked Lists Processing: Insertion, Deletion and Traversal
In a doubly linked list, each node has two links, one link to its previous node and another link to its
next node. Thus in the definition of a node structure, one more pointer, prev, is added into the node
structure, the rest is the same. Of course, at the end of a direction, there is an ending node. Here, we
specify that the first node and the last node are the ending node in each direction, respectively. It is
efficient to have head and tail nodes that point to the first node and the last node, respectively. In this
section, we still take STUDENT_DATA as an example to discuss how to process doubly linked lists.
The STUDENT_DATA node structure for a doubly linked list is defined in the file, st_data.h, all
necessary global declarations library files, and header files are included in the file, header.h. We
will discuss five operations as given in the file, operation.h, on a doubly linked list.
In the following, we describe each operation, define each function and give their implementations in
C and finally provide you a complete source code of an example that can test each function. The
source program is given in Appendix 7.2.
To create a doubly linked list node, it is to allocate memory for the node structure defined in the file
"st_data.h" and to return a pointer to this memory area. The node has two pointers (next) and (prev)
to a null reference, respectively.
operation.h
header.h
typedef struct s_data{
char student_name[14];
int student_ID;
float student_height;
struct s_data *next;
struct s_data *prev;
}STUDENT_DATA;
#incude <stdio.h>
#include <stdlib>
#include <malloc.h>
#include “st_data.h”
static STUDENT_DATA *head;
st_data.h
- Create a list node
- Add a node to the end of a list
- Insert a node in the middle of a list
- Remove a node from a list
- Traverse through a list
To add a node to a doubly linked list, it is to insert the node at the end of the list as shown in Figure
7.17. Since there is a link of the head node, which is directly linked to the last node, searching for the
last node is not necessary. If the list is empty, both links of the head node are linked to the new node
as shown in the line 4 and line 5. Otherwise the link, prev, of the head node is changed to point to
the new node, the previous last node points to the new node, and the new node becomes current last
node as seen in the line 8, line 9, and line 10 below.
#include "header.h"
STUDENT_DATA *create_a_node() {
STUDENT_DATA *p;
p = (STUDENT_DATA *)malloc(sizeof (STUDENT_DATA ));
if (p == NULL) {
printf("Failed: run out of memory! ¥n");
exit(1);
}
p->next = NULL;
p->prev = NULL;
return p;
}
1.
#include "header.h"
2.
void add_node_to_end(STUDENT_DATA *new){
3.
if (head->prev == NULL) {
4.
head->next = new;
5.
head->prev = new;
6.
}
7.
else{
8.
head->prev->next = new;
9.
new->prev = head->prev;
10. head->prev = new;
11.
}
12.
}
To insert a node to a doubly linked list, it is to insert a node to a specified location in the list. It is
normally to insert a node after a specified node. First it is necessary to find the specified node in the
list, and then insert the new node after it. Instead of changing two links in a singly linked list,
insertion of a node after a specified node in a doubly linked list
has to change four links. The
function that inserts a node, node_y after the node, node_x, is given below. As we can see that if the
specified node, node_x, is the last node,insertion of the node, node_y, becomes insertion of a node
to the end of the list. Thus, it can simply call the function, add_node_to_end(), which was just
described above. If the specified node, node_x, is the head node, then the special handling for the
link, prev, of the head is necessary. That is both links of the head node have to point to the new node,
node_y.
#include "header.h"
void insert_node_after(STUDENT_DATA *node_y,
STUDENT_DATA *node_x){
if (node_y == NULL|| node_x == NULL||
node_y == node_x || node_x ->next == node_y) {
printf("insert_a_node_after:bad arguments¥n");
return;
}
if (node_x->next == NULL) /* node_x is the last node*/
add_node_to_end(node_y);
else if (node_x == head) { /* node_x is head node*/
node_y->next = node_x->next;
node_x ->next->prev = node_y;
node_y->prev = NULL;
node_x->next = node_y;
} else { /* node_x is in the list */
node_y->next = node_x->next;
node_x->next->prev = node_y;
node_y->prev = node_x;
node_x->next = node_y;
}
}
To delete a node from a doubly linked list, it is to find the proceeding node (node_x) of the node
(node_y) to be deleted, delete node_y and to free up the memory used by the deleted node, node_y.
If the node to be deleted is the first node or the last node, the handling of two links of the head node
is necessary. Otherwise in the situation as shown in Figure 7.19, deletion of the node in the list
(neither the first node nor the last node) is simply to add two new links and free the deleted node.
To traverse forward through a doubly linked list, it is the same as the traverse through a singly linked
list. To traverse backward through a doubly linked list, it is similar but starts at the last node in the
list.
#include "header.h"
void delete_a_node(STUDENT_DATA *node_y){
if (head->next == node_y){
/*first node */
node_y->next->prev = NULL;
head->next = node_y->next;
free(node_y);
}
else if (head->prev == node_y) {
/*last node */
node_y->prev->next = NULL;
head->prev = node_y->prev;
free(node_y);
}
else{
/*middle node*/
node_y->prev->next = node_y->next;
node_y ->next->prev = node_y->prev;
free(node_y);
}
}
The complete source program of an example that does the testing of all functions introduced in
section is provided in Appendix 7.2 at the end of this Chapter. This program reads records in data
file record.dat (that is given in Appendix 7.3) and adds each record one by one to the end of the
singly linked list. You can insert a new record to the list after any node (in the program we insert a
new record after the first node but you can replace the first node by any other node), and delete any
record in the doubly linked list (in the program we delete the new node but you can replace the new
node by any other specified node). The traverse forward and backward functions print the student ID
which they traverse.
7.3.2 Implementing Deques with Doubly Linked Lists
In this section, we will introduce double-ended queues and operations on a double-ended queue. A
double-ended queue is the extension of a queue, which is also called a deque. A deque data structure
allows insertion and deletion at both the front and the rear of a queue. A deque node structure is
defined in a file, deque_node.h.
#include "header.h"
void traverse_forward(){
STUDENT_DATA *p;
for (p = head; p!=NULL; p= p->next)
printf("student ID = %d ¥n", p->student_ID);
}
void traverse_backward(){
STUDENT_DATA *p;
for (p = head; p!=NULL; p= p->prev)
printf("student ID = %d ¥n", p->student_ID);
}
typedef int ITEM_type;
#define MAXSIZE 10
typedef struct deque_node {
ITEM_type item;
struct deque_node *next;
struct deque_node *prev;
}DEQUE_NODE;
static DEQUE_NODE *head;
deque_node.h.
The basic operations of a deque described in this section are insertion and deletion of a
DEQUE_NODE at both ends of a doubly linked list. The function,
make_a_node(), makes it
possible to process an item directly by making a new node with the given item. The processing of a
deque becomes the processing of nodes in a doubly linked list. Readers may find the functions
presented here are quite similar to the functions in the last section.
To make a new node with a given item, it is to allocate memory space for a deque node and assign
the given item to the node’s item field and set null reference to both links of the deque node, and
then to return the allocated memory location to the node pointer.
Before carrying on operations on a deque, we have to initialize it, that is to say, the head node of a
doubly linked list at beginning is allocated with memory and point to the null reference. The function,
deque_initialize(), is presented below.
The function, deque_add_at_front(), is to create a new node with the given data item and insert the
node at the front of the deque, that is insert the new node after the head node as shown in Figure
7.21.
#include "deque_node.h"
DEQUE_NODE *make_a_node(ITEM_type item) {
DEQUE_NODE *p;
p = (DEQUE_NODE *)malloc(sizeof (DEQUE_NODE));
if (p == NULL) {
printf(“run out of memory!.¥n”);
exit(1);
}
p->item = item;
p->next = NULL;
p->prev = NULL;
return p;
}
#include "deque_node.h"
void deque_initialize() {
head = (DEQUE_NODE *)malloc(sizeof (DEQUE_NODE));
if (head == NULL) {
printf(“run out of memory!.¥n”);
exit(1);
}
head->next = NULL;
head->prev = NULL;
}
The function checks whether the deque is empty or not. In the case of empty, the inserted new node
is the last node as well. Thus both links of the head node, next and prev, point to the new node.
We can also add a data item from the end of a deque. The function, deque_add_at_rear(), allows a
new node with the given item to be inserted at the rear of the deque. When the deque is empty, the
new node is processed in the same way as it is in the function, deque_add_at_front().
#include "deque_node.h"
void deque_add_at_front(ITEM_type item){
DEQUE_NODE *new_node;
new_node=make_a_node(item);
if(new_node == NULL)
printf("Failed: push a nonexistent node!¥n");
else if (head -> next == NULL) {
head->next = new_node;
head->prev = new_node;
return;
}
else {
new_node ->next =head -> next;
new_node ->prev = NULL;
head->next->prev = new_node;
head->next = new_node;
}
}
There are two ways to delete a node from a deque. We can delete a node at the front or a node at the
rear. Since the head node has a link pointing to the first node and a link pointing the last node, these
two versions of deleting a node are efficient in a deque. The function, deque_add_at_front(), is to
delete the first node. If the first node is the last node as well, the deletion process becomes to free the
first node and let both the next and prev links of the head node point to the null reference. Otherwise
the prev link remains the same and the next link points the previous second node. Thus the previous
second node becomes the current first node. The prev link of the current first node has to be set with
the null reference.
#include "deque_node.h"
void deque_add_at_rear(ITEM_type item){
. DEQUE_NODE *new_node;
new_node=make_a_node(item);
if(new_node == NULL)
printf("Failed: push a nonexistent node!¥n");
else if (head -> next == NULL) {
head->next = new_node;
head->prev = new_node;
return;
}
else {
new_node->prev = head->prev;
head->prev->next = new_node;
head->prev = new_node;
}
}
In the function, deque_add_at_rear(), when the last node is the first node, it means after a deletion,
the deque becomes an empty deque such that both the prev and next links of the head node have to
point to the null reference. Otherwise it frees the previous last node and the node that is preceding
the previous last node becomes the current last node. The prev link of the head node is changed to
point to the current last node and the next link of the current last node is set with the null reference.
#include "deque_node.h"
void deque_delete_at_front(ITEM_type item){
DEQUE_NODE *front_node;
if (head->next == NULL){
printf("empty dequeue!");
exit(1);
}
else if (head->prev == head->next) {/*last node */
head->next = NULL;
head->prev = NULL;
free(head->next);
}
else {
front_node = head->next;
head->next->prev = NULL;
head->next = head->next->next;
free(front_node);
}
}
Exercises
Beginner’s Exercises:
1.
What is a structure?
2.
What is a self-referential structure?
3.
What is a link in a linked list?
4.
What is a linked stack?
5.
What is a linked queue?
6.
What are advantages of using a linked list over using an array?
Intermediate Exercises:
7.
Define a TEACHER_DATA structure with teacher’s name, course name, and number of
students in the teacher’s class.
8.
Define a STUDENT_DATA structure with student’s name, number of courses taken, and
birth date including year, month, and day.
9.
Insert a group of 10 students’ data to a singly linked list. Traverse the list and print out the
student data.
10.
Write a function to exchange arbitrary two nodes in a singly linked list.
11.
Write a function that concatenates two singly linked lists into a singly linked double-ended
list.
12.
Write a function that converts the singly linked double-ended list into a doubly linked
#include "deque_node.h"
void deque_delete_at_rear(ITEM_type item){
DEQUE_NODE *rear_node;
if (head->next == NULL){
printf("empty dequeue!");
exit(1);
}
else if (head->prev == head->next) {/*last node */
head->next = NULL;
head->prev = NULL;
free(head->next);
}
else {
rear_node = head->prev;
head->prev = rear_node->prev;
rear_node->prev->next = NULL;
free(rear_node);
}
}
double-ended list.
Advanced Exercises:
13.
Insert a group of 10 students’ data to a singly linked list and calculate the average age of the
students.
14.
Write a function to arrange a singly linked list of student data in ascending order according
to student’s age.
15.
Write an algorithm to checks correspondence of parentheses in expressions with 3 types of
parenthesis and implement the algorithm with a linked stack. For example, an expression is
as follow:
{x + (h - (j - (k - [l -n]))) * c - [(d + e)]} / (y - [a + b])
16.
Write an algorithm that can copy input sequence. (Hint: using linked stack)
17.
Write an algorithm that can reverse input sequence. (Hint: using linked queue)
18.
Write an algorithm to implement a reverse Polish calculator using a linked stack. In a
reverse Polish calculator, the operands (numbers) are entered before the operation (+, -, *, /)
is specified. Therefore, the operands are pushed onto a linked stack. When an operation is
performed, it pops its operands from the linked stack and pushes its result back onto the
linked stack. For example,
3 5 + 2 /
means
(3*5) /(1+2)
The figure below shows each state of the linked stack in each step. As it can be seen that a
reverse Polish calculator is that any expression, no matter how complicated, can be specified
without the use of parentheses.
Appendices
Appendix 7.1. The Source Program in C of Implementation of a Singly Linked List
/* Implementation of a singly linked list */
/* slist.c */
#include
#include
#include
#include
#define MAXLEN 10
static STUDENT_DATA *head;
typedef struct s_data{
int student_ID;
char student_name[14];
float student_height;
struct s_data *next;
}STUDENT_DATA;
STUDENT_DATA *create_a_node();
void add_a_node_end(struct s_data *new);
void insert_a_node_after(struct s_data *new, struct s_data *node_x);
void delete_a_node(STUDENT_DATA *node_y);
STUDENT_DATA *find_a_node_ID(int id);
STUDENT_DATA *find_a_node_name(char name);
void print();
main (){
int i,ID;
char name[10];
STUDENT_DATA *p,*new,*tmp1,*tmp2;
FILE *fp;
new=(STUDENT_DATA *)malloc(sizeof(STUDENT_DATA));
if ((fp=fopen("record","r"))==NULL) exit(0);
for (i=0;istudent_ID,p->student_name,&p->student_height);
add_a_node_end(p);
}
print(head);
printf ("Please input the new element:");
scanf (" %d %s %f",&new->student_ID,new->student_name,&new->student_height);
insert_a_node_after(new,head);
print(head);
delete_a_node(new);
print(head);
tmp1=(STUDENT_DATA *)malloc(sizeof(STUDENT_DATA));
printf("Please input the ID:");
scanf("%d",&ID);
tmp1=find_a_node_ID(ID);
printf(" %d %s %f\n",tmp1->student_ID,tmp1->student_name,tmp1->student_height);
tmp2=(STUDENT_DATA *)malloc(sizeof(STUDENT_DATA));
printf("Please input student name:");
scanf("%s",&name);
tmp2=find_a_node_name(name);
printf(" %d %s %f\n",tmp2->student_ID,tmp2->student_name,tmp2->student_height);
fclose(fp);
}
STUDENT_DATA *create_a_node() {
STUDENT_DATA *p;
p = (STUDENT_DATA *)malloc(sizeof (STUDENT_DATA ));
if (p == NULL){
printf("Failed: run out of memory!\n");
exit(1);
}
p ->next = NULL;
return p;
}
void add_a_node_end(STUDENT_DATA *new){
STUDENT_DATA *p;
for (p = head; p->next != NULL; p = p->next)
;
p->next = new;
}
void insert_a_node_after(STUDENT_DATA *new, STUDENT_DATA *node_x){
if (new == NULL|| node_x == NULL|| new == node_x
|| node_x ->next == new ) {
printf("Bad arguments\n");
return;
}
if(node_x->next == NULL) /* check if it is the last node */
add_a_node_end(new);
else{
new->next = node_x->next; /* add link_a*/
node_x->next = new; /* change link_b to link_c*/
}
}
void delete_a_node(STUDENT_DATA *node_y){
STUDENT_DATA *p;
if (node_y == head->next) /* head is the node proceeding node_y */
head->next = node_y->next;
else{ /* find the node p proceeding node_y */
for (p=head; ((p != NULL) &&(p->next != node_y)); p = p->next)
;
if (p == NULL){ /* check if node p exists */
printf("Failure: can not find node_y!");
return;
}
p->next = p->next->next;
/* delete two links (link_a and link_b) and add one link link_c*/
}
free(node_y);
}
STUDENT_DATA *find_a_node_ID(int id){
STUDENT_DATA *p;
for( p=head; p != NULL; p = p->next )
if ( p->student_ID == id)
return p;
return NULL;
}
STUDENT_DATA *find_a_node_name(char name){
STUDENT_DATA *p;
for( p=head; p != NULL; p = p->next )
if (strcmp( p->student_name, name)==0)
?????? return p;
return NULL;
}
void print(STUDENT_DATA *head)
{
STUDENT_DATA *p;
if (head!=NULL)
{
printf("Now these records are:\n");
for ( p=head;p!=NULL;p=p->next)
printf(" %d %s %f\n",p->student_ID,p->student_name,p->student_height);
}
else
printf("\n It is a null list!\n");
}
Appendix 7.2. The Source Program in C of Implementation of a Doubly Linked List
/* Implementation of a doubly linked list */
/* dlist.c */
#include
#include
#include
#define MAXLEN 5
typedef struct s_data{
int student_ID;
char student_name[14];
float student_height;
struct s_data *next;
struct s_data *prev;
}STUDENT_DATA;
STUDENT_DATA *create_a_node();
void add_a_node_to_end(STUDENT_DATA *node);
void insert_a_node_after(STUDENT_DATA *node_y,STUDENT_DATA *node_x);
void delete_a_node(STUDENT_DATA *node);
void traverse_forward();
void traverse_backward();
void print();
static STUDENT_DATA *head;
main(){
int i,ID;
STUDENT_DATA *p,*new,*tmp;
FILE *fp;
head=(STUDENT_DATA *)malloc(sizeof(STUDENT_DATA));
head->next = NULL;
head->prev = NULL;
new=(STUDENT_DATA *)malloc(sizeof(STUDENT_DATA));
tmp=(STUDENT_DATA *)malloc(sizeof(STUDENT_DATA));
if ((fp=fopen("record","r"))==NULL) exit(0);
for (i=0;istudent_ID,p->student_name,&p->student_height);
add_a_node_to_end(p);
}
print(head);
tmp=head->next;
printf ("Please input the new element:");
scanf (" %d %s %f",&new->student_ID,new->student_name,&new->student_height);
insert_a_node_after (new,tmp);
print(head);
delete_a_node(new);
print(head);
traverse_forward();
traverse_backward();
fclose(fp);
}
STUDENT_DATA *create_a_node() {
STUDENT_DATA *p;
p = (STUDENT_DATA *)malloc(sizeof (STUDENT_DATA ));
if (p == NULL) {
printf("Failed: run out of memory! \n");
exit(1);
}
p->next = NULL;
p->prev = NULL;
return p;
}
void add_a_node_to_end(STUDENT_DATA *node){
if (head->prev == NULL) {
head->next = node;
head->prev = node;
}
else{
head->prev->next = node;
node->prev = head->prev;
head->prev = node;
}
}
void insert_a_node_after(STUDENT_DATA *node_y, STUDENT_DATA *node_x){
if (node_y == NULL|| node_x == NULL|| node_y == node_x || node_x ->next == node_y )
{
printf("insert_a_node_after:bad arguments\n");
return;
}
if (node_x->next == NULL)
add_a_node_to_end(node_y);
else if (node_x == head)
{
node_y->next = node_x->next;
node_x->next->prev = node_y;
node_y->prev = NULL;
node_x->next = node_y;
}
else{
node_y ->next = node_x->next;
node_x ->next->prev = node_y;
node_y ->prev = node_x;
node_x ->next = node_y;
}
}
void delete_a_node(STUDENT_DATA *node_y){
STUDENT_DATA *p;
if (node_y== head){ /*head node*/
printf("attempt to delete a head node!");
return;
}
else if (head->next == node_y){ /*first node */
node_y->next->prev = NULL;
head->next = node_y->next;
free(node_y);
}
else if (head->prev == node_y) { /*last node */
node_y->prev->next = NULL;
head->prev = node_y->prev;
free(node_y);
}
else{ /*middle node*/
node_y->prev->next = node_y->next;
node_y->next->prev = node_y->prev;
free(node_y);
}
}
void traverse_forward(){
STUDENT_DATA *p;
for (p = head; p!=NULL; p= p->next)
printf("student ID = %d \n", p->student_ID);
}
void traverse_backward(){
STUDENT_DATA *p;
for (p = head; p!=NULL; p=p->prev)
printf("student ID = %d \n", p->student_ID);
}
void print(STUDENT_DATA *head)
{
STUDENT_DATA *p;
if (head!=NULL)
{
printf("Now these records are:\n");
for ( p=head;p!=NULL;p=p->next)
printf(" %d %s %f\n",p->student_ID,p->student_name,p->student_height);
}
else
printf("\n It is a null doubly linked list!\n");
}
Appendix 7.3. record.dat
950127 camel 1.60
950136 liapi 1.75
950150 muzhi 1.55
950152 totoh 1.60
950176 zhaoc 1.80
References
1.
R. Sedgewick, Algorithms in C, Addison-Wesley, 1990.
2.
M.A. Weiss, Data Structures and Algorithm Analysis in C (Second Edition),
Addison-Wesley, 1997.
3.
R. Kruse, C.L. Tondo, and B. Leung, Data Structures and Program Design in C (second
Edition), Prentice-Hall, 1997.
4.
Micheal T. Goodrich and Roberto Tamassia, Data Structures and Algorithms in JAVA,
ISBN0-471-19308-9, John Wiley & Sons, Inc., 1998.