Intermediate C Programming

Chapter 19

Programming Problems Using Linked List

19.1 Queues . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 307

19.2 Sorting Numbers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 308

19.3 Sparse Arrays . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 308

19.4 Reversing a Linked List . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 314

19.1 Queues

The function List insert in Section 18.3 always inserts the new value at the beginning

of the list. If we always delete nodes from the front of the list, then the linked list is a

stack. In this problem we change the insert function so that the ﬁrst inserted value is at

the beginning of the list and the latest inserted value is at the end of the list. If we still

remove elements from the beginning of the list we have created a queue, like a line at a store

waiting for service. The implementation below uses recursion.

Node * List_i nsert ( Node * head , i nt val )1

i f ( head == NULL )3

return Nod e_cons t ruct ( val ) ;5

head -> next = List_i nsert ( head -> next , val ) ;7

return head ;8

When the if condition is (when head is NULL), the list is empty. Every recursive call

moves forward by following the next link. This condition can be true if the function has

reached the end of the list. When the frame from the call stack is popped, the previous

node’s next is set to a pointer to the newly created node. For nodes not at the end, line 7

is essentially head -> next = head -> next without changing the list.

You may have noticed that this particular linked list implementation of a queue is not

eﬃcient. Every time a node is inserted, the function has to go through the entire list to

reach the end of the list. This is unavoidable because the program only tracks the beginning

of the list. One solution is to keep track of both the beginning (the head) and the end (the

tail) of the list. This requires two pointers.

Another problem is that the links are uni-directional. When deleting a node, it is nec-

essary to keep track of the node before the node to be deleted. This inconvenience can be

solved by using two links in each node: next and previous. If q is p -> next, then p is

q -> previous. The head of the list has no previous node so its previous points to NULL.

The tail of the list has no next node so its next points to NULL. This is called a doubly linked

list. The structure deﬁnition for a node in a doubly linked list is shown below:

307

308 Intermediate C Programming

typedef s t ru ct listnode1

st ruc t listnode * next ;3

st ruc t listnode * previous ;4

int value ;5

} Node ;6

19.2 Sorting Numbers

This problem asks you to modify List insert so that the values in the list are sorted

in the ascending order. This function is similar to the previous one, except for lines 8 to 12.

If val is smaller, it should be inserted before head. Otherwise, it should be inserted after

head, as handled by line 13.

Node * List_i nsert ( Node * head , i nt val )1

Node * ptr = Nod e _const ruct ( val ) ;3

i f ( head == NULL )4

return ptr ;6

i f (( head -> value ) > val )8

ptr -> next = head ;10

return ptr ;11

}12

head -> next = List_i nsert ( head -> next , val ) ;13

return head ;14

}15

This and the previous problems use the call stack to keep head. When the recursive

function returns, head is unchanged.

19.3 Sparse Arrays

Arrays are widely used in many applications, but sometimes most of the elements are

zeros. Storing these elements wastes memory. A sparse array stores only those elements

whose values are non-zero. This problem asks you to write a program managing spare

arrays: Each node stores one pair of index and value. The program reads two sparse arrays

from two ﬁles, merges the arrays, and stores the new array in a ﬁle. How are two arrays

merged?

• If one index exists in one array and is not in the other array, then this element is

added to the new array.

• If the same index exists in both arrays, the values are added. If the value is zero, then

Programming Problems Using Linked List 309

the element is deleted. If the value is not zero, then the element is added to the new

array.

The diagram below illustrates what happens when we join two sparse arrays. Each

element is expressed by an index–value pair.

Array 1

index 0 102 315

value 5 −5 8

Array 2

index 11 102 315

value 2 5 2

Array 1 + Array 2

index 0 11 315

value 5 2 10

The index 102 is not in the new array because the value becomes zero after the two

arrays are joined. To test this implementation, we want to read sparse arrays from disk.

For simplicity, we can assume that in each input ﬁle the indexes are distinct. Each line of

the ﬁle contains two integers: index and value. The two integers are separated by space.

The indexes stored in a ﬁle are not necessarily sorted. The header ﬁle is shown below. The

header ﬁle declares four functions:

// sparse . h1

#i f n d e f SPARSE_H2

#d ef in e SPARSE_H3

typedef s t ru ct linked {4

int index ;5

int value ;6

st ruc t linked * next ;7

} Node ;8

// read a sparse array from a file and return the array9

// return NULL if reading fails10

Node * List_read ( char * fi l ename );11

// write a sparse array to a file12

// return 1 if success , 0 if fail13

int List_save ( char * filename , Node * arr );14

// merge two sparse arrays15

// the two input arrays are not changed and the new array16

// does not share memory with the input arrays17

Node * List_me r ge ( Node * arr1 , Node * arr2 ) ;18

// release all nodes in a sparse array19

void List_d estroy ( Node * arr );20

#e ndif21

Below is a sample implementation of these four functions. Even though the indexes from

input ﬁles are not sorted, the linked lists are sorted by the indexes.

// sparse . c1

#in clude " sparse .h "2

#in clude < stdio .h >3

#in clude < stdlib .h >4

s t a t i c Node * Node_ c reate ( i n t ind , i nt val );5

s t a t i c Node * List_ i nsert ( Node * head , i n t ind , i n t val ) ;6

s t a t i c Node * List_copy ( Node * head ) ;7

Node * List_read ( char * fi l ename )8

310 Intermediate C Programming

FILE * fptr = fopen ( filename , "r ");10

i f ( fptr == NULL )11

{12

return NULL ;13

}14

int ind ;15

int val ;16

Node * head = NULL ;17

while ( fscanf ( fptr , " %d %d" , & ind , & val ) == 2)18

{19

head = List_i nsert ( head , ind , val );20

}21

fclose ( fptr );22

return head ;23

}24

int List_save ( char * filename , Node * arr )25

{26

FILE * fptr = fopen ( filename , "w ");27

i f ( fptr == NULL )28

{29

return 0;30

}31

while ( arr != NULL )32

{33

fprintf ( fptr , " %d %d \n" , arr -> index , arr -> value );34

arr = arr -> next ;35

}36

fclose ( fptr );37

return 1;38

}39

Node * List_me r ge ( Node * arr1 , Node * arr2 )40

{41

Node * arr3 = List_cop y ( arr1 );42

while ( arr2 != NULL )43

{44

arr3 = List_i nsert ( arr3 , arr2 -> index ,45

arr2 -> value );46

arr2 = arr2 -> next ;47

}48

return arr3 ;49

}50

void List_d estroy ( Node * arr )51

{52

i f ( arr == NULL )53

{54

return ;55

}56

while ( arr != NULL )57

{58

Node * ptr = arr -> next ;59

free ( arr );60

Programming Problems Using Linked List 311

arr = ptr ;61

}62

}63

s t a t i c Node * Node_ c reate ( i n t ind , i nt val )64

{65

Node * nd = malloc ( s i z e o f ( Node ) );66

i f ( nd == NULL )67

{68

return NULL ;69

}70

nd -> index = ind ;71

nd -> value = val ;72

nd -> next = NULL ;73

return nd;74

}75

// If the same index appears again , add the value76

// The return e d list is sorted by the index .77

s t a t i c Node * List_ i nsert ( Node * head , i n t ind , i n t val )78

{79

i f ( val == 0) // do not insert zero value80

{81

return head ;82

}83

i f ( head == NULL )84

{85

return Node _ create ( ind , val ) ;86

}87

i f (( head -> index ) > ind )88

{89

// insert the new node before the list90

Node * ptr = Node_ create ( ind , val );91

ptr -> next = head ;92

return ptr ;93

}94

i f (( head -> index ) == ind )95

{96

// merge the nodes97

head -> value += val ;98

i f (( head -> value ) == 0)99

{100

// delete this node101

Node * ptr = head -> next ;102

free ( head );103

return ptr ;104

}105

return head ;106

}107

head -> next = List_i nsert ( head -> next , ind , val );108

return head ;109

}110

Node * List_copy ( Node * arr )111

Previous Chapter

18. Linked Lists (3/3)

Next Chapter

19. Programming Problems Using Linked List (2/2)

Table of Contents for Intermediate C Programming

Table of Contents for
Intermediate C Programming