Microsoft PowerPoint – 12_Linked_Lists_in_C
O
SU
C
SE
2
42
1
J.E.Jones
Required Reading: Pointers On C, Chapter 12, Sections
12.1 through 12.2.2
O
SU
C
SE
2
42
1
J. E. Jones
Previously, we saw how to declare a struct with a pointer to a struct of the same
type. This kind of struct variable can be used as a node in a linked list. The node
typically has two members:
– One member, called data, is a C struct which is used to store data of interest.
– The other member, called next, is a pointer to a struct Node. For example:
struct Data {
char first_name[15];
char last_name[15];
int idNumber;
};
typedef struct Node{
struct Data student;
struct Node *next;
}Node;
The linked list will be constructed by creating a number of these nodes
dynamically, one at a time, and linking them to each other with the next pointer.
Note that within typedef creation for Node,
we must use struct Node * because the
typedef is not yet complete.
O
SU
C
SE
2
42
1
J. E. Jones
The structure of a linked list is more complicated than an
array, and more work is required to construct and maintain a
linked list.
Nonetheless, depending on the application, linked structures
often have advantages.
Some say Linear linked structures (linked lists) are not so
commonly used in real applications (I disagree), but they are
simpler to construct and manipulate than binary (search) trees,
so we will only work with a linear, singly-linked list here.
Binary search trees have significant advantages compared with
(sorted) arrays in many cases, such as faster insertion and
deletion times, but comparable search performance.
O
SU
C
SE
2
42
1
J. E. Jones
Using the nodes that we have introduced before, what else do we need to
construct a linked list?
Only one thing: Node * list_head, to point to the first node in the list:
Node *list_head = NULL; /*Set list head pointer to NULL initially
to show list is empty */
We only want the Node * rather than a whole Node here to keep space efficiently.
NOTE: This is different from Java where you just use an empty node
To construct the list, we will make the list_head pointer point to the first
node, the next member of the first node point to the second node, . . . . the
next member of the n – 1st node point to the nth (last) node, and the next
member of the nth (last) node point to no node (make it a NULL pointer).
Making the next member of the last node point to NULL will allow us to
detect where the end of the list is (and avoid segmentation faults!). This is
analogous to ending a character string with a NULL character.
O
SU
C
SE
2
42
1
J. E. Jones
Before we look at the details of insertion into the list, we need to consider
the list_head pointer more carefully.
Various functions will have to know the address in the list_head pointer in
order to do things with the list (insert nodes, delete nodes, process data in
the nodes, print data in the nodes, etc.).
If we make the list_head pointer a file scope (“global”) variable, we do not
have to pass it as a parameter to these functions.
◦ This, however, is currently an unacceptable way to write software and should
only be done in very limited cases (this is not one of them)! Debugging and
maintenance are MUCH more difficult with global variables.
You are not allowed to use file scope variables in software you write for
this course.
Therefore, in general, the functions in your linked list program will have to
be passed the list_head pointer, which is declared in main, as a parameter,
if they need to access data in the list or modify the list in any way.
The challenge for each of you is to determine whether the list_head
pointer should be passed by value or by reference to each function that
requires it.
O
SU
C
SE
2
42
1
J. E. Jones
We need to think about whether the function may
need to modify (change) the list_head pointer or if it
only needs to read it.
If it needs to potentially modify it, we cannot pass the
head pointer by value. Why?
Which functions might need to modify the head
pointer? Keep this question in mind as we look at the
following slides.
O
SU
C
SE
2
42
1
J. E. Jones
/* Here are the necessary declarations for a Node of the type declared above, and for
a head pointer */
struct Data {
char first_name[15];
char last_name[15];
int id_number;
int first_semester;
struct grades *list;
};
typedef struct Node {
struct Data student;
struct Node *next;
}Node;
scanf(“%s”, (newNodePtr->student.first_name));
/*Initialize list_head to NULL since list is empty at first. */
Node *list_head = NULL;
Note: no structures of type Node have yet been declared or dynamically allocated,
only space for a head pointer has been allocated.
These can be put in a .h file
This must be a block scope variable
O
SU
C
SE
2
42
1
J. E. Jones
/*With the declarations above, to create a new Node, we can use the following */
Node *newNodePtr;
newNodePtr = (Node *)malloc (sizeof (Node));
if (newNodePtr == NULL) {
. . . . /*The storage was NOT allocated, so print an error message and exit */
}
else {
. . . . /* The storage was allocated, and we can use the Node */
. . . . /* Call a function to get the data for the node and store it in the node */
getDataForNode(newNodePtr); /* why can we just pass the Node address?
why we don’t need to pass &newNodePtr ? */
}
/* then we can put this new Node into the linked list */
insertNode(&list_head, newNodePtr);
Note: When we read the data from input which is to be stored in the node, we can read it directly into
the node (how?), rather than storing it in another variable, and then assigning that variable to the
node.
O
SU
C
SE
2
42
1
J. E. Jones
White space can be an issue, since scanf() can read both numeric data (ints and
floats) and non-numeric data (strings).
Keep in mind that scanf() ignores leading white space characters (space, tab, etc.)
for numeric data, but not for non-numeric data in the way we will read it (we will
be reading strings which have white space characters).
Therefore, if you are reading numeric data, you do not have to be concerned about
consuming preceding newlines, because scanf() will take care of it for you (it
“consumes” any whitespace characters before the 1st digit).
◦ Where might you find a “preceding newline” ?????
If you are reading non-numeric data, however, you will have to consume any
preceding newlines, because scanf() will not consume them.
◦ You’ve seen this in each lab so far, but I wanted to remind you again
O
SU
C
SE
2
42
1
J. E. Jones
Typically, we want a list in some sorted order so you
must identify what value your linked list node contains
that you want to use as your sort key
Once you have determined your sort key, you must
decide how to represent your key so that your sort order
is quick to calculate
◦ How would you create a sort key for month/day/year when
multiple years are involved?
For example, years 1950 through (potentially) 2099.
Thoughts?
O
SU
C
SE
2
42
1
J. E. Jones
Would this work???
union date_key {
int key; /* a 4-byte key */
struct{
char day; /* 1-31 */
char month; /* 1-12 */
short year; /*1950-2099 */
}
}dateKey;
O
SU
C
SE
2
42
1
J. E. Jones
union date_key {
int key; /* a 4-byte key*/
struct{
char day; /* 1-31, these values fit in 8 bits */
char month; /* 1-12, these values fit in 8 bits */
short year; /* 1950-2099, these values fit in 16 bits */
}
}dateKey;
-2w-1 through 2w-1-1 says these values fit
8-bits 8-bits 16-bits
dateKey.key=0x07CC0815 = 130,811,925
note this only works in Little Endian, so not portable
1-31 1-12 1950-2099
0001 0101
(21)
0000 1000
(8)
1100 1100 0000 0111
(1996)
O
SU
C
SE
2
42
1
J. E. Jones
What about just int dateKey; ???
Can we still put in separate fields???
16-bits 8-bits 8-bits
This is the way it would look if we were just reading the value from
left to right.
1-311-121950-2099
0001 0101
(21)
0000 1000
(8)
0000 0111 1100 1100
(1996)
O
SU
C
SE
2
42
1
J. E. Jones
int dateKey;
int day, month, year;
scanf(“%d/%d/%d”, &month, &day, &year);
Input: 8/21/1996
dateKey=year;
dateKey <<=16; month <<=8; dateKey |=month; dateKey |=day; dateKey=0x07CC0815 = 130,811,925 note this works in Big or Little Endian 0000 0000 0000 0000 0000 1000 0000 0000 0000 0000 0000 0000 0000 0111 1100 1100 0000 0111 1100 1100 0000 0000 0000 0000 0000 0111 1100 1100 0000 1000 0000 0000 0000 0111 1100 1100 0000 1000 0001 0101 0000 0111 1100 1100 0000 1000 0001 0101 (1996) (8) (21) O SU C SE 2 42 1 J. E. Jones int dateKey; int day, month, year; year = dateKey; year = (unsigned)year >>16;
month = dateKey;
month &=0x0000ff00;
month = (unsigned)month>>8;
day= dateKey;
day &=0x000000ff;
Why do we have to cast year and month to unsigned??
0000 0000 0000 0000 0000 1000 0000 0000
0000 0000 0000 0000 0000 0111 1100 1100
0000 0111 1100 1100 0000 1000 0001 0101
0000 0111 1100 1100 0000 1000 0001 0101
0000 0000 0000 0000 0000 0000 0000 1000
0000 0111 1100 1100 0000 1000 0001 0101
0000 0000 0000 0000 0000 0000 0001 0101
O
SU
C
SE
2
42
1
J. E. Jones
If we want to insert a node into the list, what do we need to do?
We will assume that the nodes in the list will be ordered in ascending order
based on some member in the data member of the node (assume it’s an
integer).
First, we have to create the new node (as shown above), and initialize the
members of the data member of the Node
Then, we have to call the insert function, and pass it the current list (how?),
and the new node (how?).
In the insert function, declare a pointer to traverse (go through) the list:
Node *traversePtr;
Set the traversePtr to point to the same address the list_head pointer points
to, so that you start looking at the beginning of the list.
How might we do these things??
O
SU
C
SE
2
42
1
J. E. Jones
If we want to insert a node into the list, what do we need to do?
We will assume that the nodes in the list will be ordered in ascending order
based on some member in the data member of the node (assume it’s an
integer).
First, we have to create the new node (as shown above), and initialize the
members of the data member of the Node
Then, we have to call the insert function, and pass it the current list (how?),
and the new node (how?). insert(&list_head, newNodePtr);
◦ Prototype for insert function would be
insert(Node **list_head_ptr, Node *newNodePtr);
In the insert function, declare a pointer to traverse (go through) the list:
Node *traversePtr;
Set the traversePtr to point to the same address the list_head pointer points
to, so that you start looking at the beginning of the list.
traversePtr = *list_head_ptr;
O
SU
C
SE
2
42
1
J. E. Jones
When we traverse the list to determine where to insert, there are three
possible cases or situations:
1) The list is empty (list_head is a NULL pointer).
– To insert, make list_head point to the inserted node. That is,
list_head = address of node we wish to insert.
if(*list_head_ptr == NULL) then *list_head_ptr =
newNodePtr;
– Make the next pointer of the inserted node point to NULL (it
may have been initialized to NULL during data entry, but if not,
this needs to be done here).
newNodePtr->next = NULL;
O
SU
C
SE
2
42
1
J. E. Jones
list_head_ptr Node *list_head
newNodePtr NULL
NULL
next
O
SU
C
SE
2
42
1
J. E. Jones
*list_head_ptr = newNodePtr;
list_head_ptr list_head
newNodePtr NULL
next
O
SU
C
SE
2
42
1
J. E. Jones
2) The list already has one or more nodes, and the new node needs to be inserted
as the first node in the list.
– How?
IN THIS ORDER
A. The current address in list_head must be copied to the *next member in the
newNodePtr structure
newNodePtr->next = *list_head_ptr;
B. The value of list_head must be changed to the address of newNodePtr.
*list_head_ptr = newNodePtr;
O
SU
C
SE
2
42
1
J. E. Jones
newNodePtr->next = *list_head_ptr;
list_head_ptr list_head
newNodePtr
NULL
Prior to executing the instruction above, this is what we
have
next
next
O
SU
C
SE
2
42
1
J. E. Jones
newNodePtr->next = *list_head_ptr;
list_head_ptr list_head
newNodePtr
NULL
At this point, both list_head and newNodePtr->next point to the
same place
next
next
O
SU
C
SE
2
42
1
J. E. Jones
*list_head_ptr = newNodePtr;
list_head_ptr list_head
newNodePtr
NULL
Now list_head points to newNodePtr; and
newNodePtr->next points to all following Nodes
next
next
O
SU
C
SE
2
42
1
J. E. Jones
3. Non-exception case. i.e. The new Node belongs somewhere between two existing
Nodes.
– we traverse the list to search for where to insert the node. To do so,
we must maintain a pointer to the node before the node where we are
(see below):
Node *priorNode;
– use the traversePtr previously declared to point to the Node we are
currently looking at
– So, traverse the list, node by node, to find out the correct place to insert the
node based on our sort key;
advance traversePtr and priorNode through the list.
– When traversing, we need to check that the traverse pointer is not NULL
before trying to access members of the node to which it points. If it is NULL,
we have reached the end of the list, and should insert the new node there (as
described below).
– When the correct place is found, change these pointers (in this order!):
a. The next pointer of the node to be inserted:
newNodePtr->next = traversePtr;
b. The next pointer of the node after which the new node is being inserted
(this is priorNode->next): priorNode->next = newNodePtr;
O
SU
C
SE
2
42
1
J. E. Jones
priorNode traversePtr
newNodePtr
next next
next
O
SU
C
SE
2
42
1
J. E. Jones
newNodePtr->next = traversePtr;
priorNode traversePtr
newNodePtr
At this point both priorNode and newNodePtr point to
traversePtr
next next
next
O
SU
C
SE
2
42
1
J. E. Jones
priorNode->next = newNodePtr;
priorNode traversePtr
newNodePtr
At this point newNodePtr is inserted in the linked list
next next
next
O
SU
C
SE
2
42
1
J. E. Jones
If we want to delete a node from the list, what do we need to
do?
Declare a pointer to traverse the list:
Node *traversePtr;
Set the traversePtr to point to the same address the list_head
pointer points to.
traversePtr = *list_head_ptr;
O
SU
C
SE
2
42
1
J. E. Jones
When we traverse the list to find the node to be deleted, there are 3 possible
situations:
1. The list is empty: ERROR – There are no nodes, so there is nothing to
be deleted! Print an error message informing the user that they have tried
to delete a non-existent node.
O
SU
C
SE
2
42
1
J. E. Jones
2. Node to delete is at the front of the linked list
– Check to see if the node to be deleted is the first node. If so, in order to
delete it, do these things, in this order:
Make the list_head pointer point to the same thing as
traversePtr->next, then free(traversePtr);
traversePtr = *list_head_ptr;
*list_head_ptr = traversePtr->next;
OR
*list_head_ptr = (*list_head_ptr)->next;
then
free(traversePtr);
O
SU
C
SE
2
42
1
J. E. Jones
list_head_ptr Node *list_head
traversePtr
next next
O
SU
C
SE
2
42
1
J. E. Jones
*list_head_ptr = traversePtr->next;
list_head_ptr list_head
traversePtr
next next
O
SU
C
SE
2
42
1
J. E. Jones
free(traversePtr);
list_head_ptr list_head
next
O
SU
C
SE
2
42
1
J. E. Jones
3. Non-exception case. i.e. The Node to delete is somewhere between two
existing Nodes or at the end. Both cases can be handled this way.
– traverse the list to search for the node to be deleted, we must maintain a
pointer to the node before the node where we are:
struct Node *priorNode;
– advance traversePtr and priorNode to go through the list.
– When traversing, we need to check that the traverse pointer is not NULL
before trying to access members of the node to which it points.
– If it is NULL, the node is not in the list. Print an error message to
the user.
– If the node is found, do these actions in this order:
a. Change the next pointer of prior node (the node before the node
which is being deleted): priorNode->next = traversePtr->next;
b. Call free() with the pointer to the node being deleted (what pointer
is this?).
O
SU
C
SE
2
42
1
J. E. Jones
priorNode traversePtr->next
traversePtr
Node to delete
next next
next
O
SU
C
SE
2
42
1
J. E. Jones
priorNode->next = traversePtr->next;
priorNode traversePtr->next
traversePtr
At this point, both priorNode->next and traversePtr->next point to the
same thing, but we’re getting ready to free traversePtr.
Node to delete
next next
next
O
SU
C
SE
2
42
1
J. E. Jones
Free(traversePtr);
priorNode traversePtr->next
next next
O
SU
C
SE
2
42
1
J. E. Jones
Besides insertion and deletion, there are some other kinds of operations we can
identify on linked lists:
List traversal for some purpose:
– Find an element in the list and print out the related data.
– Print all the items in the list.
– Do computations on the data in the list, such as totaling all the items,
counting the number of items in the list, computing averages, finding
minimum and maximum values, etc.
In general, traversing the list for these purposes is less complicated than it is for
insertion and deletion, because we do not have to keep track of the prior node; we
can declare a traversePtr and make it point to the beginning of the list and then go
through the entire list.
Do you think you would need to pass the list_head by reference or by value to these
type functions?
We do, however, must still ensure that we do not try to access nodes beyond the end
of the list (you should now be able to figure out how to do this)!
O
SU
C
SE
2
42
1
J. E. Jones
Before your program terminates, you should call free() to
return the space for all the nodes, which were allocated as the
program was running.
Best practice is to m/calloc() a node just as you need the space
and call free() for each node as soon as there is no longer a
need for it. Think of pulling a paper cup from the stack, using
it, then throwing it away when done.
I’ve had students put together a neat little recursive function to
free Nodes from a linked list prior to their program ending, but
there is a much simpler, less resource costly way to do it by
just traversing down the linked list freeing Nodes as you go.
O
SU
C
SE
2
42
1
J. E. Jones
Node *traversePtr; *priorNode;
traversePtr = *list_head_ptr;
while(traversePtr!=NULL){
◦ Look at key; is this the spot to add/delete Node? Break out.
◦ No? Keep looking;
priorNode = traversePtr;
traversePtr = traversePtr->next;
}
◦ Add/delete Node in list