### Chapter 9

```Chapter 9
Abstract Model of a List Obj.
Handling the Back of the List
Designing a New LL Structure
Insertion into a List
Inserting a Node at a Position
(2 slides)
Linked List (LL) nodes (2 slides)
Circular Doubly LL’s (2 slides)
Node Composition
Updating a Doubly LL
Inserting at the Front of a LL
Summary Slides (5 slides)
Deleting from the Front of a LL
Removing a Target Node
1
Main Index
Contents
Abstract Model of a List Object
front
2
back
Main Index
Contents
Insertion Into a List by Shifting
Vector Storage Elements
Insert 5 into list 2 7 3 10 at the 3rd position
Implementation shifts listVector[2] and listVector[3]
2
7
3
10
Resulting list 2 7 5 3 10
Implementation assigns 5 to listVector[2]
2
3
7
5
3
Main Index
10
Contents

Each Node is like a piece of a chain
Individual Piece

Pop Chain
To insert a new link, break the chain at the
desired location and simply reconnect at both
ends of the new piece.
Disconnect
Reconnect
4
Main Index
Contents

Removal is like Insertion in reverse.
Disconnect
Reconnect
5
Main Index
Contents

Node Composition
An individual Node is composed of two parts, a
Data field containing the data stored by the
node, and a Pointer field that marks the
address of the next Node in the list.
nodeValue
next
nodeValue
6
next
Main Index
Contents
Inserting at the Front of a
Before
After
front
front
back
newNode
Before
front
item
(a)
20
55
front
After
(b)
front
item
20
55
front
7
Main Index
Contents
Deleting From the Front of a
front
//
front = NULL
Deleting front of a 1-node list
front
//
front = front->next
Deleting front of a multi-node list
8
Main Index
Contents
Removing a Target Node
front
next
//
prev
9
Main Index
target
curr
Contents
//
Handling the Back of the List
top
front
D
C
B
D
A
C
B
Stack
10
Main Index
Contents
A
Structure
front
...
back
//
item
//
newNode
11
Main Index
Contents
Inserting a Node at a Position
next
1
prevNode = curr->prev
3
prev
prev
2
4
item
curr
next
newNode
12
Main Index
Contents
Inserting a Node at a Position
1
//
//
prevNode = curr->prev
prev
next
succNode = curr->next
curr
2
13
Main Index
//
//
Contents

A Watch Band provides a good Real Life
analogue for this Data Structure
First Element
Last Element
Second Element
14
Main Index
Contents

Implemented on a Computer it might look
something like this.
3
2
4
15
Main Index
Contents
9
Before Insert: Empty list
prev
next
After Iinsert: List with one element
prev
next
newNode
16
Main Index
Contents
Summary Slide 1
- Each node contains a value and a pointer to the
next node in the list.
- The list begins with a pointer to the first node of
the list and terminates when a node has a NULL
pointer.
17
Main Index
Contents
Summary Slide 2
§- Inserting/Deleting at the front of a singly
1)Insert
- Set the pointer in the new node to the previous
value of front.
- update front to point at the new node.
2)Erase
- assign front the pointer value of the first node,
and then delete the node.
18
Main Index
Contents
Summary Slide 3
§- Inserting/Erasing inside a singly linked
list
- Maintain a pointer to the current list node and a
pointer to the previous node.
- Change the pointer value in the previous node.
19
Main Index
Contents
Summary Slide 4
§- Insert/Delete at the back of a singly
- Maintain a pointer to the last list node that has
value NULL when the list is empty.
- Assign a “back” pointer the address of the first
- To add other nodes at the back:
1) allocate a new node
2) assign the pointer in node “back” to point to the new
node
3) assign the pointer “back” the address of the new node.
20
Main Index
Contents
Summary Slide 5
- provide the most flexible implementation for the
sequential list.
§- Its nodes have pointers to the next and the previous
node, so the program can traverse a list in either the
forward or backward direction.
- Traverse a list by starting at the first node and
follow the sequence of next nodes until you arrive