Chapter 4

Linked Lists
Yi-Fen Liu
Department of IECS, FCU

References:
- E. Horowitz, S. Sahni and S. Anderson-Freed, Fundamentals of Data Structures (2nd Edition)
- Slides are credited from Prof. Chung, NTHU
 Outline
• Pointers
• Singly Linked Lists
• Dynamically Linked Stacks and Queues
• Polynomials
• Chain
• Circularly Linked Lists
• Equivalence Relations
• Doubly Linked Lists
Yi-Fen Liu, FCU IECS Data Structures (Ch4) - 2
POINTERS
 Pointers (1)
• Consider the following alphabetized list
– (bat, cat, sat, vat)
• If we store this list in an array
– Add the word mat to this list
• move sat and vat one position to the right before we insert mat.
– Remove the word cat from the list
• move sat and vat one position to the left
• Problems of a sequence representation (ordered list)
– Arbitrary insertion and deletion from arrays can be very time-
consuming
– Waste storage

Yi-Fen Liu, FCU IECS Data Structures (Ch4) - 4

 Pointers (2)
0 1 2 3 4 5 6 7 8 9
list: 10 20 30 40 50
move= 5
Insert 25

0 1 2 3 4 5 6 7 8 9
list: 10 20 30
25 40
30 50
40 50
move= 4
Delete 20
0 1 2 3 4 5 6 7 8 9
list: 10 20
25 25
30 30
40 40
50 50

move = 5
 Pointers (3)
• An elegant solution: using linked representation
– Items may be placed anywhere in memory
• Store the address, or location, of the next element in that list
for accessing elements in the correct order with each element
– The list element is a node which contains both a data component and
a pointer to the next item in the list
– The pointers are often called links

Yi-Fen Liu, FCU IECS Data Structures (Ch4) - 6

 Pointers (4)
• C provides extensive supports for pointers
• Two most important operators used with the pointer type
– & the address operator
– * the dereferencing (or indirection) operator
• Example
– int i, *pi;
• then i is an integer variable and pi is a pointer to an integer
– If we say “pi = &i;”
• then &i returns the address of i and assigns it as the value of pi
– To assign a value to i we can say
• i = 10; or *pi = 10;

Yi-Fen Liu, FCU IECS Data Structures (Ch4) - 7

 Pointers (5)
• Pointers can be dangerous
– It is a wise practice to set all pointers to NULL when they are not actually
pointing to an object
– Using explicit type cast when converting between pointer types
– Example
• pi = (int *) malloc(sizeof(int));
/*assign to pi a pointer to int*/
• pf = (float *)pi;
/*casts int pointer to float pointer*/
– In many systems, pointers have the same size as type int
• Since int is the default type specifier, some programmers omit the
return type when defining a function
• The return type defaults to int which can later be interpreted as a
pointer

Yi-Fen Liu, FCU IECS Data Structures (Ch4) - 8

 Pointers (6)
• Using dynamically allocated storage
– When programming, you may not know how much space you will
need, nor do you wish to allocate some vary large area that may
never be required
• C provides heap, for allocating storage at run-time
• You may call a function, malloc, and request the amount of
memory you need
• When you no longer need an area of memory, you may free it by
calling another function, free, and return the area of memory to
the system

Data Structures (Ch4) - 9 9

SINGLY LINKED LIST
 Singly Linked Lists (1)
• Linked lists are drawn as an order sequence of
nodes with links represented as arrows
– The name of the pointer to the first node in the list
is the name of the list

Yi-Fen Liu, FCU IECS Data Structures (Ch4) - 11

 Singly Linked Lists (2)
• The nodes do not resident in sequential locations
• The locations of the nodes may change on different
runs
ptr

... Null
Link Field
Node
Data Field

chain
Data Structures (Ch4) - 12
 Singly Linked Lists (3)
• Why it is easier to make arbitrary insertions
and deletions using a linked list?
– To insert the word mat between cat can sat, we
must
• Get a node that is currently unused; let its address be paddr
• Set the data field of this node to mat
• Set paddr’s link field to point to the address found in the link field
of the node containing sat
• Set the link field of the node containing cat to point to paddr

bat cat sat vat NULL

paddr mat
Data Structures (Ch4) - 13
 Singly Linked Lists (4)
• Delete mat from the list
– We only need to find the element that immediately precedes mat,
which is cat, and set its link field to point to sat’s link
– We have not moved any data, and although the link field of mat
still points to sat, mat is no longer in the list

Yi-Fen Liu, FCU IECS Data Structures (Ch4) - 14

 Singly Linked Lists (5)
• We need the following capabilities to make linked
representations possible
– Defining a node’s structure, that is, the fields it contains.
We use self-referential structures, discussed in Chapter 2
to do this
– Create new nodes when we need them (malloc)
– Remove nodes that we no longer need (free)

Yi-Fen Liu, FCU IECS Data Structures (Ch4) - 15

 Singly Linked Lists (6)
• Self-Referential Structures
– One or more of its components is a pointer to itself
– typedef struct list {
char data;
list *link;
}
– list item1, item2, item3; Construct a list with three nodes
item1.data=‘a’; item1.link=&item2;
item2.data=‘b’; item2.link=&item3;
item3.data=‘c’; malloc: obtain a node (memory)
item1.link=&item2;
item2.link=&item3; free: release memory
item3.link=NULL;
a b c
Data Structures (Ch4) - 16
 Singly Linked Lists (7)
• Example: List of words
typedef struct listNode *listPointer;
typedef struct listNode {
char data [4];
listPointer link;
};
– Creation
• listPointer ptr = NULL;
– Testing
• #define IS_EMPTY(ptr) (!(ptr))
– Allocation
• ptr = (listPointer) malloc (sizeof(listNode));
– Return the spaces
• free(ptr);

Yi-Fen Liu, FCU IECS Data Structures (Ch4) - 17

 Singly Linked Lists (8)
• Example: Two-node linked list
typedef struct listNode *listPointer;
typedef struct listNode {
int data;
listPointer link; #define IS_FULL(ptr) (!(ptr))
};
listPointer ptr =NULL; When returns NULL if there is no more memory.
• Program : Create a two-node list
listPointer create2( )
{
/* create a linked list with two nodes */
listPointer first, second;
first = (listPointer) malloc(sizeof(listNode));
second = (listPointer) malloc(sizeof(listNode));
second -> link = NULL;
second -> data = 20;
first -> data = 10;
first ->link = second;
return first;
} 10 20 NULL

first second
 Singly Linked Lists (9)
• Insertion
– Observation
• insert a new node with data = 50 into the list ptr
after node
ptr 10 20 NULL
node

50

temp
Yi-Fen Liu, FCU IECS Data Structures (Ch4) - 19
 Singly Linked Lists (10)
• Implement Insertion
void insert(listPointer *ptr, listPointer node)
{
/* insert a new node with data = 50 into the list
ptr after node */
listPointer temp;
temp=(listPointer)malloc(sizeof(listNode));
if(IS_FULL(temp)){
fprintf(stderr, “The memory is full\n”);
exit(1);
}
temp->data=50; temp 50
 Singly Linked Lists (11)
if(*ptr){ //nonempty list
temp->link = node->link;
node->link = temp;
}
else{ //empty list
temp->link = NULL;
*ptr = temp;
}
ptr
} 10 20 NULL
node

50

temp
 Singly Linked Lists (12)
• Deletion
– Observation: delete node from the list

ptr trail node

10 50 20 NULL

ptr trail node

10 50 20 NULL

ptr

10 20 NULL
 Singly Linked Lists (13)
• Implement Deletion:
void delete(listPointer *ptr, listPointer trail,
listPointer node)
{
/* delete node from the list, trail is the preceding node
ptr is the head of the list */
if(trail)
trail->link = node->link;
else
*ptr = (*ptr)->link;
ptr trail node
free(node);
}
10 50 20 NULL

Data Structures (Ch4) - 23

 Singly Linked Lists (14)
• Print out a list (traverse a list)
– Program: Printing a list
void print_list(listPointer ptr)
{
printf(“The list contains: “);
for ( ; ptr; ptr = ptr->link)
printf(“%4d”, ptr->data);
printf(“\n”);
}

Yi-Fen Liu, FCU IECS Data Structures (Ch4) - 24

DYNAMICALLY LINKED STACKS AND
QUEUES
Dynamically Linked Stacks and
Queues
• Both stack and the queue are easy insertion and
deletion of nodes by using link list
– Easily add or delete a node form the top of the stack
– Easily add a node to the rear of the queue and add or delete a
node at the front of a queue
 Dynamically Linked Stacks (1)
 Represent n stacks Stack

top item link

link

...
NULL

Yi-Fen Liu, FCU IECS Data Structures (Ch4) - 27

 Dynamically Linked Stacks (2)
• Push in the linked stack
void add(stack_pointer *top, element item){
/* add an element to the top of the stack */
stack_pointer temp = (stack_pointer) malloc
(sizeof (stack));
if (IS_FULL(temp)) {
fprintf(stderr, “ The memory is full\n”);
exit(1);
} temp item link
temp->item = item;
temp->link = *top; top link
*top= temp;
} link

...
NULL
Data Structures (Ch4) - 28
 Dynamically Linked Stacks (3)
• Pop from the linked stack
element delete(stack_pointer *top) {
/* delete an element from the stack */
stack_pointer temp = *top;
element item;
if (IS_EMPTY(temp)) {
fprintf(stderr, “The stack temp
is empty\n”);
exit(1); top item link
}
item = temp->item; link
*top = temp->link;
free(temp); link
return item;

...
}
NULL

Data Structures (Ch4) - 29

 Dynamically Linked Queues (1)
• Represent n queues

Queue
front item link
Delete from
link

...
Add to
rear NULL
Data Structures (Ch4) - 30
 Dynamically Linked Queues (2)
• enqueue in the linked queue

front link
link

...
rear NULL

temp item NULL

 Dynamically Linked Queues (3)
• dequeue from the linked queue (similar to push)

temp
front item link

link
link

...
rear NULL
 Dynamically Linked Stacks and
Queues
• The solution presented above to the n-stack,
m-queue problem is both computationally and
conceptually simple
– We no longer need to shift stacks or queues to
make space
– Computation can proceed as long as there is
memory available

Yi-Fen Liu, FCU IECS Data Structures (Ch4) - 33

POLYNOMIALS
 Polynomials (1)
• Representing polynomials as singly linked lists
– In general, we want to represent the polynomial
A( x )  am 1 x em 1      a0 x e0
• Where the ai are nonzero coefficients and the ei are
nonnegative integer exponents such that
em-1 ＞ em-2 ＞ … ＞ e1 ＞ e0 ≧ 0
– We will represent each term as a node containing
coefficient and exponent fields, as well as a
pointer to the next term

Yi-Fen Liu, FCU IECS Data Structures (Ch4) - 35

 Polynomials (2)
• Assuming that the coefficients are integers, the type
declarations are
typedef struct poly_node *poly_pointer;
typedef struct poly_node {
int coef;
int expon; a  3 x 14
 2 x8
1
poly_pointer link;
};
poly_pointer a,b,d; b  8x14  3x10  10x 6
• Draw poly_nodes as
coef expon link

Data Structures (Ch4) - 36

 Polynomials (3)
• Adding Polynomials
– To add two polynomials, we examine their terms
starting at the nodes pointed to by a and b
• If the exponents of the two terms are equal
– add the two coefficients
– create a new term for the result
• If the exponent of the current term in a is less than b
– create a duplicate term of b
– attach this term to the result, called d
– advance the pointer to the next term in b.
• We take a similar action on a if a->expon > b->expon

Yi-Fen Liu, FCU IECS Data Structures (Ch4) - 37

 Polynomials (4)
Generating the first three terms of d = a+b
 Polynomials (5)

Yi-Fen Liu, FCU IECS Data Structures (Ch4) - 39

Polynomials
(6)
 Polynomials (7)
• Attach a node to the end of a list
void attach(float coefficient, int exponent, poly_pointer *ptr){
/* create a new node with coef = coefficient and expon = exponent,
attach it to the node pointed to by ptr. Ptr is updated to point to
this new node */
poly_pointer temp;
temp = (poly_pointer) malloc(sizeof(poly_node));
/* create new node */
if (IS_FULL(temp)) {
fprintf(stderr, “The memory is full\n”);
exit(1);
}
temp->coef = coefficient; /* copy item to the new node */
temp->expon = exponent;
(*ptr)->link = temp; /* attach */
*ptr = temp; /* move ptr to the end of the list */
}

Yi-Fen Liu, FCU IECS Data Structures (Ch4) - 41

 Polynomials (8)
• Analysis of padd
A( x )(  am 1 x em 1      a0 x e0 )  B( x )(  bn 1 x f n 1    b0 x f 0 )
– coefficient additions
0  additions  min(m, n)
where m (n) denotes the number of terms in A (B).
– exponent comparisons
extreme case:
em-1 > fm-1 > em-2 > fm-2 > … > e1 > f1 > e0 > f0
m+n-1 comparisons
– creation of new nodes
extreme case:
maximum number of terms in d is m+n (m + n new nodes)
summary: O(m+n)

Yi-Fen Liu, FCU IECS Data Structures (Ch4) - 42

 Polynomials (9)
• A Suite for Polynomials read_poly()
e(x) = a(x) * b(x) + d(x) print_poly()
poly_pointer a, b, d, e; padd()
... psub()
a = read_poly(); pmult()
b = read_poly();
d = read_poly();
temp is used to hold a partial result.
temp = pmult(a, b); By returning the nodes of temp, we
may use it to hold other polynomials
e = padd(temp, d);
print_poly(e);

Yi-Fen Liu, FCU IECS Data Structures (Ch4) - 43

 Polynomials (10)
• Erase Polynomials
– erase frees the nodes in temp
void erase (poly_pointer *ptr){
/* erase the polynomial pointed to by ptr */
poly_pointer temp;
while ( *ptr){
temp = *ptr;
*ptr = (*ptr) -> link;
free(temp);
}
}

Yi-Fen Liu, FCU IECS Data Structures (Ch4) - 44

CHAIN
 Chain (1)
• Chain
– A singly linked list in which the last node has a null link
• Operations for chains
– Inverting a chain
• For a list of length ≧1 nodes, the while loop is executed length times
and so the computing time is linear or O(length).

... NULL

lead
invert

× ...
NULL

lead
 Chain (2)

Two extra pointers

trial

middle
lead middle
lead trial NULL

...

NULL
 Chain (3)
• Concatenates two
chains
– Concatenates two chains,
ptr1 and ptr2.
– Assign the list ptr1
followed by the list ptr2.

O(length of list ptr1)

temp

NULL NULL

ptr1 ptr2
CIRCULARLY LINKED LISTS
 Circularly Linked Lists
• Circular Linked list
– The link field of the last node points to the first
node in the list
• Example
– Represent a polynomial ptr = 3x14+2x8+1 as a
circularly linked list

ptr 3 14 2 8 1 0

Yi-Fen Liu, FCU IECS Data Structures (Ch4) - 50

 Maintain an Available List (1)
• We free nodes that are no longer in use so
that we may reuse these nodes later
• We can obtain an efficient erase algorithm for
circular lists, by maintaining our own list (as a
chain) of nodes that have been “freed”
• Instead of using malloc and free, we now use
get_node and ret_node
avail ... NULL

List of freed nodes

Maintain an Available List (2)
• When we need a new node, we examine this list
– If the list is not empty, then we may use one of its nodes.
– Only when the list is empty we have to use malloc to
create a new node
 Maintain an Available List (3)
• Insert ptr to the front of this list
– Let avail be a variable of type poly_pointer that points to the first
node in our list of freed nodes
– Henceforth, we call this list the available space list or avail list
– Initially, we set avail to NULL

Yi-Fen Liu, FCU IECS Data Structures (Ch4) - 53

 Maintain
an Available List (4)
• Erase a circular list in a
fixed amount (constant)
of time O(1) independent
of the number of nodes
in the list using cerase

ptr      

temp

avail      NULL

紅色link所連接而成的 chain
Polynomial Representations (1)
• We must handle the zero polynomial as a special case
– To avoid it, we introduce a head node into each polynomial
– Each polynomial, zero or nonzero, contains one additional node
– The expon and coef fields of this node are irrelevant
Polynomial
Representations
/* head node */
(2)
• For fit the circular
list with head node
/*a->expont > -1, b->expont > -1 */
representation
– We may remove
the test for (*ptr)
from cerase (p.168)
– Changes the
original padd to /* link to the first node */
cpadd
 Circularly Linked Lists (1)
• Operations for circularly linked lists
– Question
• What happens when we want to insert a new node at
the front of the circular linked list ptr?

ptr x1 x2 x3
– Answer
• move down the entire length of ptr.
– Possible Solution

x1 x2 x3 ptr
 Circularly Linked Lists (2)
• Insert a new node at
the front of a circular
list
• To insert node at the
rear, we only need to
add the additional
statement *ptr = node
to the else clause of
insert_front

x1 x2 x3 ptr

node
 Circularly Linked Lists (3)
• Finding the length of a circular list

Yi-Fen Liu, FCU IECS Data Structures (Ch4) - 59

EQUIVALENCE RELATIONS
 Equivalence Relations (1)
• Reflexive Relation
– For any polygon x, x ≡ x (e.g., x is electrically equivalent to itself)
• Symmetric Relation
– For any two polygons x and y, if x ≡ y, then y ≡ x
• Transitive Relation
– For any three polygons x, y, and z, if x ≡ y and y ≡ z, then x ≡ z
• Definition
– A relation over a set, S, is said to be an equivalence relation over S iff it
is symmetric, reflexive, and transitive over S
• Example
– “equal to” relationship is an equivalence relation

Yi-Fen Liu, FCU IECS Data Structures (Ch4) - 61

 Equivalence Relations (2)
• Example
– If we have 12 polygons numbered 0 through 11
0  4, 3  1, 6  10, 8  9, 7  4, 6  8, 3  5, 2  11, 11  0
we can partition the twelve polygons into the following equivalence
classes
{0, 2, 4, 7, 11}, {1, 3, 5}, {6, 8, 9,10}
• Two phases to determine equivalence
– First phase: the equivalence pairs (i, j) are read in and stored
– Second phase:
• We begin at 0 and find all pairs of the form (0, j)
Continue until the entire equivalence class containing 0 has been
found, marked, and printed
– Next find another object not yet output, and repeat the above process

Yi-Fen Liu, FCU IECS Data Structures (Ch4) - 62

 Equivalence Relation (3)
• Program to find equivalence classes
#include <stdio.h>
void main(void){ #define MAX_SIZE 24
short int out[MAX_SIZE];
#define IS_FULL(ptr) (!(ptr))
node_pointer seq[MAX_SIZE];
node_pointer x, y, top; #define FALSE 0
int i, j, n; #define TRUE 1
printf(“Enter the size (<=%d) ”, MAX_SIZE);
scanf(“%d”, &n);
for(i=0; i<n; i++){
/*initialize seq and out */
out[i] = TRUE;
seq[i] = NULL;
} typedef struct node *node_pointer;
/* Phase 1 */ typedef struct node {
/* Phase 2 */ int data;
}
node_pointer link;
};
Data Structures (Ch4) - 64
 Equivalence Relations (4)
• Phase 1: read in and store the equivalence pairs <i, j>
[0] 11 4 NULL

[1] 3 NULL

[2] 11 NULL
[3] 5 1 NULL

[4] 7 0 NULL
(1) (2)
[5] 3 NULL Insert x to the top of lists seq[i]
[6] 8 10 NULL
[7] 4 NULL

[8] 6 9 NULL

[9] 8 NULL

[10] 6 NULL
Insert x to the top of lists seq[j]
[11] 0 2 NULL

0  4, 3  1, 6  10, 8  9, 7  4, 6  8, 3  5, 2  11, 11  0
 Equivalence Relations (5)
• Phase 2
– Begin at 0 and find all pairs of the form <0, j>,
where 0 and j are in the same equivalence class
– By transitivity, all pairs of the form <j, k> imply
that k in the same equivalence class as 0
– Continue this way until we have found, marked,
and printed the entire equivalent class containing
0

Yi-Fen Liu, FCU IECS Data Structures (Ch4) - 65

 Equivalence Relations (6)
x
y [0] [1] [2] [3] [4] [5] [6] [7] [8] [9] [10] [11]

 Phase 2 i= 1
0 j= 11
7
2
4
0 out:
top
[0] 11 4 NULL

[1] 3 NULL

[2] 11 NULL
[3] 5 1 NULL

[4] 7 0 NULL

[5] 3 NULL

[6] 8 10 NULL
[7] 4 NULL

[8] 6 9 NULL

[9] 8 NULL

[10] 6 NULL

[11] 0 2 NULL

New class: 0 11 4 7 2
DOUBLY LINKED LISTS
 Doubly Linked Lists (1)
• Singly linked lists pose problems because we can
move easily only in the direction of the links
... NULL

? ptr
• Doubly linked list has at least three fields
– left link field (llink), data field (item), right link field (rlink)
– The necessary declarations
typedef struct node *node_pointer;
typedef struct node{
node_pointer llink;
element item;
node_pointer rlink;
};
Data Structures (Ch4) - 68
 Doubly Linked Lists (2)
• Sample
– doubly linked circular with head node

Yi-Fen Liu, FCU IECS Data Structures (Ch4) - 69

 Doubly Linked Lists (3)
– empty double linked circular list with head node

– suppose that ptr points to any node in a doubly

linked list, then:
• ptr = ptr -> llink -> rlink = ptr -> rlink -> llink

Yi-Fen Liu, FCU IECS Data Structures (Ch4) - 70

 Doubly Linked Lists (4)

Insert a node

Head node

node

llink item rlink

New node
 Doubly Linked Lists (5)

Delete a node

Head node

llink item rlink

deleted node