PowerPoint Presentation
Data Structures: A Pseudocode Approach with C
1
2
Array
Linear List
Implementations
Linked List
3
Linked Lists
Dummy Node[s]
Header
Singly-Linked Lists
Circularly-Linked Lists
Doubly-Linked Lists
Multi-Linked Lists
4
Singly Linked List
List pointer followed by linked data nodes.
5
Dummy Node[s]
Header
Singly-Linked Lists
Circularly-Linked Lists
Doubly-Linked Lists
Multi-Linked Lists
Linked Lists
6
Dummy Node
The first node in a singly-linked list.
It does not carry any data.
It is an empty data node.
7
Advantages:
It simplifies the code: since pList never changes, it does not have to be updated by insert/delete.
Also, insert/delete are more efficient: no if statement to check if the new node is to be inserted in the beginning.
8
Linked Lists
Dummy Node[s]
Header
Singly-Linked Lists
Circularly-Linked Lists
Doubly-Linked Lists
Multi-Linked Lists
9
Header
– is a structure that contains
metadata about the list, such as
-a counter,
-a pointer to the first node in the list,
-a pointer to the last node in the list, etc.
Data Structures: A Pseudocode Approach with C
10
Data Structures: A Pseudocode Approach with C
11
Data Structures: A Pseudocode Approach with C
12
Data Structures: A Pseudocode Approach with C
13
Data Structures: A Pseudocode Approach with C
14
Data Structures: A Pseudocode Approach with C
15
Data Structures: A Pseudocode Approach with C
16
Data Structures: A Pseudocode Approach with C
17
Data Structures: A Pseudocode Approach with C
18
Data Structures: A Pseudocode Approach with C
19
Data Structures: A Pseudocode Approach with C
20
Data Structures: A Pseudocode Approach with C
21
22
Dummy Node[s]
Header
Singly-Linked Lists
Circularly-Linked Lists
Doubly-Linked Lists
Multi-Linked Lists
Linked Lists
Data Structures: A Pseudocode Approach with C
23
24
Dummy Node[s]
Header
Singly-Linked Lists
Circularly-Linked Lists
Doubly-Linked Lists
Multi-Linked Lists
Linked Lists
Data Structures: A Pseudocode Approach with C
25
Data Structures: A Pseudocode Approach with C
26
Data Structures: A Pseudocode Approach with C
27
28
Dummy Node[s]
Header
Singly-Linked Lists
Circularly-Linked Lists
Doubly-Linked Lists
Multi-Linked Lists
Linked Lists
Data Structures: A Pseudocode Approach with C
29
Data Structures: A Pseudocode Approach with C
30
Linked Lists ADTs
/docProps/thumbnail.wmf
Data Structures: A Pseudocode Approach with C
1
Chapter 5
Chapter 5
Objectives
Upon completion you will be able to:
•
Explain the design, use, and operation of a linear list
•
Implement a linear list using a linked list structure
•
Understand the operation of the linear list ADT
•
Write application programs using the linear list ADT
•
Design and implement different link
–
list structures
General Linear Lists
General Linear Lists