Chapter 18
Linked Lists
18.1 Expandable Types . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 293
18.2 Linked Lists . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 294
18.3 Inserting Data . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 295
18.4 Searching a Linked List . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 297
18.5 Deleting from a Linked List . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 298
18.6 Printing a Linked List . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 302
18.7 Destroying a Linked List . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 303
18.1 Expandable Types
In the previous chapters we described two common ways to allocate memory. The first
is static allocation. The advantage of static allocation is that there can be no memory leaks;
however, the size of the array must be known at the time when the program is written. For
example
int arr [100];1
This creates an array with 100 elements.
In many cases, the size is unknown when the program is compiled; however, it is known
after the program starts executing. This is the second scenario. An example is shown below,
where the size is given by the user:
int * arr2 ;1
int length ;2
printf (" Please enter the length of the array : ");3
scanf (" %d" , & length ) ;4
arr2 = malloc ( length * s i z e o f ( in t ) );5
This scenario is often used when reading data from a file. One common strategy is to:
1. Read the file once to determine how much memory is needed.
2. Allocate the required memory.
3. Call fseek to return to the beginning of the file.
4. Read the file again and store the data in the allocated memory.
This chapter describes how to handle another common scenario: when it is impractical
or impossible to know the size even after the program starts. Memory must be allocated
and released on an as-needed basis. This is a very common scenario.
Imagine that you are creating a social network system. How many users will register? It
is possible that there will be millions of users but we have no direct control over who signs
up. We cannot have a pre-determined number, say five million users, and reject registrations
after there are already five million users. Perhaps we could allocate enough memory for a
few billions users, enough for the foreseeable future. It is wasteful. Moreover, users may
come and go. Some users register but forget their passwords and then create new accounts.
293
294 Intermediate C Programming
It may be necessary to remove accounts that have not been used for more than one year.
To manage this type of application, we must be able to allocate memory on an as-needed
basis. Memory usage must grow and shrink as the demands of the application require. This
chapter describes how to use dynamic structures. The book covers only the basic concepts
and does not give enough knowledge required to actually build a social network site. The
information in this chapter, however, provides a foundation.
If data structures, such as arrays, need to change size as programs run, we can create
a new larger (or smaller) array, copy the data, and then free the old array. Section 17.2
gives an example of an auto-resizing array: If too many digits are inserted, the array’s size
doubles. This chapter explains how to create a simple data structure that is designed to
grow without copying the existing data. It supports the following functions:
• Insert: add new data, and allocate memory as needed.
• Search: determine whether a piece of data has already been inserted.
• Delete: remove data and release memory if it is no longer needed.
• Print: print the stored data.
• Destroy: delete everything before the program ends.
The simple data structure is called a linked list, and is an example of dynamic structures
and is also an example of container structures. Such structures may contain different types
of data (int, char, Person ...). The code to insert, search, delete, print, and destroy is
quite similar for each different type. The next chapter will describe another type of container
structure called the binary tree.
18.2 Linked Lists
A linked list is a collection of nodes that are linked together by pointers. Each node is
an object with at least two attributes:
• A pointer to another node. By convention, this attribute is called next. If a given
node does not have a “next” node, then the next attribute stores NULL.
• Some data. This attribute may be a pointer, an object, or a primitive type such as
int, char, or double.
Below is an example structure, with two attributes, used as a node in a linked list. For
simplicity, the data attribute is an integer.
typedef s t ru ct listnode1
{2
st ruc t listnode * next ;3
int value ;4
} Node ; // do not forget ;5
This introduces the concept of a “self-referring structure”. Notice how next is a pointer to
struct listnode? That is what makes it self-referring. Because the C compiler reads source
files from top to bottom, it cannot see the type name Node at the time next is declared.
Thus, we assign a temporary type name: struct listnode. It is possible to refer to the
nodes as struct listnode; however, the structure is called Node from now on. Fig. 18.1
shows three views for the first operation in creating a linked list.
The diagrammatic view in (b) is the most commonly used. In (b), when a pointer’s value
is NULL, it is common to make it point to the “Ground” symbol used in electronics. My
experience working with students suggests that some students are more comfortable with
Linked Lists 295
Node * head = NULL;
symbol address value
head 200 NULL
head
(a) (b)
(c)
FIGURE 18.1: A linked list starts empty, i.e., without any Node. This figure shows three
views: (a) the source code view, (b) a diagram, and (c) the stack memory.
one particular view than with other views. The three views are shown simultaneously so
that we can see the relationships between the different representations.
18.3 Inserting Data
Node * head = NULL;
head = malloc(size(Node));
head -> next = NULL;
head -> value = 917;
symbol address value address value
head 200 60000 60001 917
60000 NULL
Call Stack Heap Memory
(a)
(c)
head
(b)
917
FIGURE 18.2:CreatingaNode object whose value is 917. Please note that head is a
pointer.
Fig. 18.2 shows how to create the very first node in a linked list, and assign a number
to the value attribute. Calling malloc will allocate space in heap memory for the two
attributes. Suppose malloc returns address 60000, then this value is assigned to the value
of head. The next line is:
head -> next = NULL;
1
This line assigns NULL to the node’s next attribute. Then, we assign 917 to the value
attribute, which is the data:
head -> value = 917;
1
Add space before or after -> makes no difference. We create a function List insert that
can make inserting nodes much more straightforward. The function can
• allocate memory for a new node.
• assign an address to the next attribute.
• assign a value to the value attribute.
Fig. 18.3 shows that the function can simplify inserting a node. Calling List
insert
with −504 as the argument creates one more list node and it is inserted at the beginning
of the list. Later, we will explain how to insert −504 at the end of the list. It is simpler to
insert nodes onto the front of a linked list. Please note that this means that the value stored
296 Intermediate C Programming
Node * head = NULL;
head = List_insert(head, 917);
symbol address value address value
head 200 60000 60001 917
60000 NULL
Call Stack Heap Memory
(a)
(c)
head
(b)
917
FIGURE 18.3: Replacing the three lines by using List insert.
at head must change. This is because head must be the newly inserted node that we just
allocated. Note that there is no guarantee that when calling malloc twice we will obtain
consecutive addresses. Fig. 18.4 shows a gap between the memory allocated to the two list
nodes. Fig. 18.5 shows three nodes.
Node * head = NULL;
head = List_insert(head, 917);
head = List_insert(head, -504);
symbol address value address value
head 200 75000 75001 -504
75000 60000
60001 917
60000 NULL
Call Stack Heap Memory
(a)
(c)
head
(b)
917
-504
FIGURE 18.4: Calling List insert again to insert another list node.
Here is a sample implementation of the insert function:
// A static function can be called by functions in this
1
// file only. Functions outside this file cannot call it.2
static Node * Node_construct(int val)3
{4
Node * nd = malloc( sizeof(Node));5
nd -> value = val;6
nd -> next = NULL;7
return nd;8
}9
10
Node * List_insert(Node * head, int val)11
{12
printf("insert%d
", val);13
Node * ptr = Node_construct(val);14
Linked Lists 297
Node * head = NULL;
head = List_insert(head, 917);
head = List_insert(head, -504);
head = List_insert(head, 326);
symbol address value address value
head 200 83000 83001 326
83000 75000
75001 -504
75000 60000
60001 917
60000 NULL
Call Stack Heap Memory
(a)
(c)
head
(b)
917
-504
326
FIGURE 18.5: Insert the third object by calling List insert again.
ptr -> next = head; // insert at the beginning
15
return ptr;16
}17
In the insert function we use a static function called Node construct.Prefixinga
function with static means that the function can only be used within the current file.
We mark the function static because it is called by List
insert only. This constructor
ensures that next is always initialized to NULL. Even though List
insert immediately
changes next after calling Node
construct, it is a good habit to always initialize next.
Later on, the program tests whether next is NULL to determine whether a node is the last
node in the list. Some students are eager to make their programs faster and do not always
initialize the next pointer inside Node
construct. Forgetting to initialize next to NULL is
a common and easily avoidable mistake.
In List
insert, the newly constructed node is called ptr. Sometimes students call
this variable new. This is discouraged because new has a special meaning in C++. This is
important when C and C++ programs are integrated together, which happens quite often.
Referring back to the code, line 15 puts the newly created node in front of the head of
the old list. Line 16 returns the newly created node. This makes head point to the newly
created node. Thus, the most recently added node is at the beginning of the list. When
List
insert is called again, a new list node is created and it is the beginning of the list.
The value stored at head changes again. We assume there is a gap between this new object
and the other two existing objects.
Pushing new elements onto the front of the list is rather like a “stack”. The end of
the list is always the first inserted value, and the beginning of the list is always the most
recently inserted value. To remove the first inserted value (at the very end of the list), it is
necessary to go through the entire list. If we always remove from the front, then we indeed
meet the property of a stack: first-in, last-out.
..................Content has been hidden....................
You can't read the all page of ebook, please click here login for view all page.