1
This lecture shows three linked list operation in detail. The operations
are:
2. Adding a new node in the middle of a linked list.
❐Chapter 5 introduces the often-
used data structure of linked lists.
❐This presentation shows how to
implement the most common
operations on linked lists.
Linked Lists in Action
CHAPTER 5
Data Structures and Other Objects
2
Here is a typical struct declaration that can be used to implement a
linked list of integers, as described in Section 5.1 of the text.
❐For this presentation, each node in the
linked list is a struct, as shown here.
data
15
struct Node
Declarations for Linked Lists
3
Within the struct, there is a type definition for a type called called “Item”.
The purpose of the Item data type is to tell us what kind of data resides
❐The data portion of each node is a type
called Item, defined by a typedef.
struct Node
data
15
Declarations for Linked Lists
4
Also inside each Node is a second member variable called link. The
purpose of the link member variable is to contain a pointer to the next
Node in the sequence of nodes.
Question: What appears in the link field of the final node in a linked list
such as this?
❐Each Node also contains a link field
which is a pointer to another Node.
data
15
data
7
struct Node
{
typedef int Item;
Item data;
Node *link;
};
Declarations for Linked Lists
data
10
link
link
null
link
5
When a linked list is implemented, we generally keep track of the first
Declarations for Linked Lists
❐A program can keep track of the front
node by using a pointer variable such
as head_ptr in this example.
❐Notice that head_ptr is not a Node —
it is a pointer
to a Node. data
link
10
data
link
15
data
link
7
null
head_ptr
6
Also remember that it is possible for a linked list to have no nodes at all.
Declarations for Linked Lists
❐A program can keep track of the front
node by using a pointer variable such
as head_ptr.
❐Notice that head_ptr is not a Node —
it is a pointer to a Node.
❐We represent the empty list by storing
null in the Head pointer.
head_ptr
null
7
In this lecture, I’ll show you the workings of three functions to
manipulate linked lists. The first function is called head_insert. The
purpose of the function is to insert a new entry at the front of a linked
list. The first parameter is the head point of the linked list declared here
as:
void list_head_insert(Node*& head_ptr, const Node::Item& entry);
Inserting a Node at the Front
We want to add a new entry, 13,
to the front of the linked list
shown here.
10
15
7
null
head_ptr
entry
13
8
Inserting a Node at the Front
❶Create a new node, pointed to
void list_head_insert(Node*& head_ptr, const Node::Item& entry);
9
Here is the C++ statement:
Inserting a Node at the Front
❶insert_ptr = new Node;
10
15
7
null
head_ptr
entry
13
insert_ptr
void list_head_insert(Node*& head_ptr, const Node::Item& entry);
10
Once the new node has been created, we need to place values in the
new node’s member variables. The first member variable is the new
node’s data field, where we are supposed to place a copy of the entry.
Another question: Can you write the C++ statement which will copy the
value of entry into the data field of the new node?
Inserting a Node at the Front
❶insert_ptr = new Node;
❷Place the data in the new
node’s data field.
10
15
7
null
head_ptr
entry
13
insert_ptr
13
void list_head_insert(Node*& head_ptr, const Node::Item& entry);
11
…or at least most of the answer is on this slide! The assignment
statement written here is copying entry into some location. What goes
Inserting a Node at the Front
❶insert_ptr = new Node;
❷insert_ptr->data = entry;
10
15
7
null
head_ptr
entry
13
insert_ptr
13
?
What expression appears
on the left side of the
assignment statement ?
void list_head_insert(Node*& head_ptr, const Node::Item& entry);
12
Here is the full answer. The expression on the left of the assignment
statement is:
insert_ptr->data
You can read an expression like this from left-to-right. The expression
means
Inserting a Node at the Front
❶insert_ptr = new Node;
❷insert_ptr->data = entry;
10
15
7
null
head_ptr
entry
13
insert_ptr
13
What expression appears
on the left side of the
assignment statement ?
void list_head_insert(Node*& head_ptr, const Node::Item& entry);
13
The third step of head_insert is to connect the new node to the rest of
the existing list. In other words, we will place a pointer into the link
member variable of the new node.
Inserting a Node at the Front
10
15
7
null
head_ptr
entry
13
insert_ptr
13
❶insert_ptr = new Node;
❷insert_ptr->data = entry;
❸Connect the new node to the
front of the list.
void list_head_insert(Node*& head_ptr, const Node::Item& entry);
14
Here is half of the assignment statement:
insert_ptr->link = ____________
Inserting a Node at the Front
10
15
7
null
head_ptr
entry
13
insert_ptr
13
What expression appears
on the right side of the
assignment statement ?
❶insert_ptr = new Node;
❷insert_ptr->data = entry;
➌insert_ptr->link = head_ptr;
?
void list_head_insert(Node*& head_ptr, const Node::Item& entry);
15
…here is the complete assignment statement:
insert_ptr->link = head_ptr;
Inserting a Node at the Front
10
15
7
null
head_ptr
entry
13
insert_ptr
13
What expression appears
on the right side of the
assignment statement ?
❶insert_ptr = new Node;
❷insert_ptr->data = entry;
➌insert_ptr->link = head_ptr;
void list_head_insert(Node*& head_ptr, const Node::Item& entry);
16
The head_insert function needs one last step: Making the head pointer
Inserting a Node at the Front
10
15
7
null
head_ptr
entry
13
insert_ptr
13
❶insert_ptr = new Node;
❷insert_ptr->data = entry;
➌insert_ptr->link = head_ptr;
❹Make the head_ptr point to the
new head of the linked list.
void list_head_insert(Node*& head_ptr, const Node::Item& entry);
17
The assignment statement is:
head_ptr = insert_ptr;
Inserting a Node at the Front
10
15
7
null
head_ptr
entry
13
insert_ptr
13
❶insert_ptr = new Node;
❷insert_ptr->data = entry;
➌insert_ptr->link = head_ptr;
➍head_ptr = insert_ptr;
void list_head_insert(Node*& head_ptr, const Node::Item& entry);
18
When the head_insert function returns, the linked list will have a new
node (containing 13).
Inserting a Node at the Front
❶insert_ptr = new Node;
❷insert_ptr->data = entry;
➌insert_ptr->link = head_ptr;
➍head_ptr = insert_ptr;
10
15
7
null
head_ptr
13
When the function returns, the
linked list has a new node at the
front, containing 13.
void list_head_insert(Node*& head_ptr, const Node::Item& entry);
19
Here’s the complete declaration of the head_insert function. Can you
find these things:
— the declaration of the local variable, insert_ptr
— the place where the new node is actually created?
void list_head_insert(Node*& head_ptr, const Node::Item& entry)
{
Node *insert_ptr;
insert_ptr = new Node;
insert_ptr->data = entry;
insert_ptr->link = head_ptr;
head_ptr = insert_ptr;
}
Inserting a Node at the Front
20
Before we finish the example, we should check one last thing. Does
the function work correctly if the list is initially empty? In other words, if
the head pointer is null, will the function manage to correctly add the
first node of the list?
void list_head_insert(Node*& head_ptr, const Node::Item& entry)
{
Node *insert_ptr;
insert_ptr = new Node;
insert_ptr->data = entry;
insert_ptr->link = head_ptr;
head_ptr = insert_ptr;
}
Inserting a Node at the Front
Does the function work
correctly for the empty
list ?