Worcester Polytechnic Institute
Carnegie Mellon
Linked Lists in C and C++
Professor Hugh C. Lauer
CS-2303, System Programming Concepts
(Slides include materials from The C Programming Language, 2nd edition, by Kernighan and Ritchie,
Absolute C++, by Walter Savitch, The C++ Programming Language, Special Edition, by Bjarne Stroustrup,
and from C: How to Program, 5th and 6th editions, by Deitel and Deitel)
CS-2303, A-Term 2010 Linked Lists 1
Worcester Polytechnic Institute
Carnegie Mellon
Common Data Structures in C and C++
Linked lists – Nothing specific in K&R
One-way
Doubly-linked
Circular
Trees –K&R §6.5
Binary
Multiple branches
Hash Tables – K&R §6.6
Combine arrays and linked list
Especially for searching for objects by value
CS-2303, A-Term 2010 Linked Lists in C and C++ 2
Worcester Polytechnic Institute
Carnegie Mellon
Definitions
Linked List
A data structure in which each element is dynamically allocated
and in which elements point to each other to define a linear
relationship Note: elements are usually the
Singly- or doubly-linked same type (but not always).
Variations: stack, queue, circular list
Tree
A data structure in which each element is dynamically allocated
and in which each element has more than one potential
successor
Defines a partial order
CS-2303, A-Term 2010 Linked Lists in C and C++ 3
Worcester Polytechnic Institute
Carnegie Mellon
Linked List
struct listItem {
type payload;
struct listItem *next; payload
}; next
payload
next
payload
payload next
next
CS-2303, A-Term 2010 Linked Lists in C and C++ 4
Worcester Polytechnic Institute
Carnegie Mellon
Linked List (continued)
Items of list are usually same type
Generally obtained from malloc()
Each item points to next item
Last item points to null
Need “head” to point to first item!
“Payload” of item may be almost anything
A single member or multiple members
Any type of object whose size is known at compile time
Including struct, union, char * or other pointers
Also arrays of fixed size at compile time (see p. 214)
CS-2303, A-Term 2010 Linked Lists in C and C++ 5
Worcester Polytechnic Institute
Carnegie Mellon
Usage of Linked Lists
Not massive numbers of items
Linear search is okay
Sorting not usually necessary
or sometimes not possible
Need to add and delete data “on the fly”
Even from middle of list
Items often need to be added to or deleted from the
“ends”
CS-2303, A-Term 2010 Linked Lists in C and C++ 6
Worcester Polytechnic Institute
Carnegie Mellon
Linked List (continued)
struct listItem {
type payload;
struct listItem *next;
};
struct listItem *head;
payload
next
payload
next payload
next
payload
next
CS-2303, A-Term 2010 Linked Lists in C and C++ 7
Worcester Polytechnic Institute
Carnegie Mellon
Adding an Item to a List
struct listItem *p, *q;
Add an item pointed to by q after item pointed to by p
Neither p nor q is NULL
payload
next
payload
next
payload
next payload
next
payload
next
CS-2303, A-Term 2010 Linked Lists in C and C++ 8
Worcester Polytechnic Institute
Carnegie Mellon
Adding an Item to a List
listItem *addAfter(listItem *p, listItem *q){
q -> next = p -> next;
p -> next = q;
return p; payload
} next
payload
next
payload
next payload
next
payload
next
CS-2303, A-Term 2010 Linked Lists in C and C++ 9
Worcester Polytechnic Institute
Carnegie Mellon
Adding an Item to a List
listItem *addAfter(listItem *p, listItem *q){
q -> next = p -> next;
p -> next = q;
return p; payload
} next
payload
next
payload
next payload
next
payload
next
CS-2303, A-Term 2010 Linked Lists in C and C++ 10
Worcester Polytechnic Institute
Carnegie Mellon
Question: What to do if we cannot
guarantee that p and q are non-NULL?
Adding an Item to a List
listItem *addAfter(listItem *p, listItem *q){
q -> next = p -> next;
p -> next = q;
return p; payload
} next
payload
next
payload
next payload
next
payload
next
CS-2303, A-Term 2010 Linked Lists in C and C++ 11
Worcester Polytechnic Institute
Carnegie Mellon
Adding an Item to a List
listItem *addAfter(listItem *p, listItem *q){
if (p && q) {
q -> next = p -> next;
p -> next = q;
} payload
return p;
next
}
payload
next
payload
next payload
next
payload
next
CS-2303, A-Term 2010 Linked Lists in C and C++ 12
Worcester Polytechnic Institute
Carnegie Mellon
What about Adding an Item
before another Item?
struct listItem *p;
Add an item before item pointed to by p (p != NULL)
payload
next
payload
next
payload
next payload
next
payload
next
CS-2303, A-Term 2010 Linked Lists in C and C++ 13
Worcester Polytechnic Institute
Carnegie Mellon
What about Adding an Item
before another Item?
Answer:–
Need to search list from beginning to find previous item
Add new item after previous item
CS-2303, A-Term 2010 Linked Lists in C and C++ 14
Worcester Polytechnic Institute
Carnegie Mellon
Doubly-Linked List
struct listItem {
type payload;
listItem *prev;
listItem *next;
};
struct listItem *head, *tail;
payload payload
prev next prev next payload
payload prev next
prev next
CS-2303, A-Term 2010 Linked Lists in C and C++ 15
Worcester Polytechnic Institute
Carnegie Mellon
Other Kinds of List Structures
Queue — FIFO (First In, First Out)
Items added at end
Items removed from beginning
Stack — LIFO (Last In, First Out)
Items added at beginning, removed from beginning
Circular list
Last item points to first item
Head may point to first or last item
Items added to end, removed from beginning
CS-2303, A-Term 2010 Linked Lists in C and C++ 16
Worcester Polytechnic Institute
Carnegie Mellon
Optional:–
Circular List struct listItem *head;
struct listItem *tail;
payload
payload
next
next
payload
payload
next
next
listItem *addToTail (listItem *p, listItem *tail){
if (p && tail) {
p -> next = tail -> next;
tail = tail -> next = p;
} else if (p) {
tail = p -> next = p;
}
return tail;
}
CS-2303, A-Term 2010 Linked Lists in C and C++ 17
Worcester Polytechnic Institute
Carnegie Mellon
Questions?
CS-2303, A-Term 2010 Linked Lists in C and C++ 18
