35
Pseudocode for Inserting Nodes
15
10
7
null
head_ptr
❷Otherwise (if the new node will not be first):
❐Start by setting a pointer named previous_ptr to point to the
node which is just before the new node’s position
This pointer is called
previous_ptr->link
What is the name of this
pointer ?
previous_ptr
36
Pseudocode for Inserting Nodes
15
10
7
null
head_ptr
➋Otherwise (if the new node will not be first):
❐Start by setting a pointer named previous_ptr to point to the
node which is just before the new node’s position
previous_ptr->link
points to the head
of a small linked
list, with 10 and 7
previous_ptr
37
Pseudocode for Inserting Nodes
15
10
7
null
head_ptr
❷Otherwise (if the new node will not be first):
❐Start by setting a pointer named previous_ptr to point to the
node which is just before the new node’s position.
The new node must
be inserted at the
front of this small
linked list.
13
Write one C++ statement
which will do the insertion.
previous_ptr
38
Pseudocode for Inserting Nodes
15
10
7
null
head_ptr
❷Otherwise (if the new node will not be first):
❐Start by setting a pointer named previous_ptr to point to the
node which is just before the new node’s position.
13
Write one C++ statement
which will do the insertion.
previous_ptr
head_insert(previous_ptr->link, entry);
39
Pseudocode for Inserting Nodes
❶Determine whether the new node will be the first node in
the linked list. If so, then there is only one step:
head_insert(head_ptr, entry);
❷ Otherwise (if the new node will not be first):
❐Set a pointer named previous_ptr to point to the node
which is just before the new node’s position.
❐Make the function call:
head_insert(previous_ptr->link, entry);
40
Pseudocode for Inserting Nodes
❐The process of adding a new node in the middle
of a list can also be incorporated as a separate
function. This function is called list_insert in the
linked list toolkit of Section 5.2.
41
Pseudocode for Removing Nodes
❐Nodes often need to be removed from a linked list.
❐As with insertion, there is a technique for removing
a node from the front of a list, and a technique for
removing a node from elsewhere.
❐We’ll look at the pseudocode for removing a node
from the front of a linked list.
42
Removing the Head Node
❶Start by setting up a temporary pointer named remove_ptr
to the head node.
43
Removing the Head Node
❶Set up remove_ptr.
❷head_ptr = remove_ptr->link;
44
Removing the Head Node
➊Set up remove_ptr and BeforePtr.
➋head_ptr = remove_ptr->link;
45
There is one last statement that the removal function should execute:
Removing the Head Node
➊Set up remove_ptr and BeforePtr.
➋head_ptr = remove_ptr->link;
❸delete remove_ptr; // Return the node’s memory to heap.
10 15 7
null
head_ptr
13
remove_ptr
46
Removing the Head Node
Here’s what the linked list looks like after the removal finishes.
47
❐It is easy to insert a node at the front of a list.
❐The linked list toolkit also provides a function for
inserting a new node elsewhere
❐It is easy to remove a node at the front of a list.
Summary
48
Presentation copyright 1997, Addison Wesley Longman,
For use with
Data Structures and Other Objects Using C++
by Michael Main and Walter Savitch.
Some artwork in the presentation is used with permission from Presentation Task Force
(copyright New Vision Technologies Inc) and Corel Gallery Clipart Catalog (copyright