21
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
head_ptr
entry
13 null
Does the function work
correctly for the empty
list ?
22
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
head_ptr
entry
13 null
insert_ptr
13
23
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
head_ptr
entry
13 null
insert_ptr
13
null
24
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
head_ptr
entry
13
insert_ptr
13
null
25
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
head_ptr
13
null
When the function
returns, the linked list
has one node,
containing 13.
26
Caution!
❐Always make sure that
your linked list
functions work
correctly with an
empty list.
EMPTY LIST
27
That’s the end of our head_insert function. There are two more linked
Pseudocode for Inserting Nodes
❐Nodes are often inserted at places other than the
front of a linked list.
❐There is a general pseudocode that you can follow
for any insertion function. . .
28
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);
29
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:
The function
we already wrote
head_insert(head_ptr, entry);
30
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);
A pointer
to the
head of
the list
31
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);
The data to put
in the new node
32
Pseudocode for Inserting Nodes
❷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.
33
As an example, suppose that we want to add 13 to this list, and we
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.
In this example, the
new node will be
the second node
previous_ptr
34
Pseudocode for Inserting Nodes
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
pointer ?