Transcript Linear Lists II

Chapter 5 Contd...
List
Objectives
• 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
• Application programs using the linear list ADT
• Design and implement different link-list structures
Data Structures: A Pseudocode Approach with C
1
List Search
•A list search is used by algorithms to locate data in a list.
•To insert data, we need to know the logical predecessor to the new
data.
•To delete data, we need to know the node to be deleted and identify
it’s logical predecessor.
•To retrieve data, we need to search the list and find the data.
•Sequential search is used for list search because there is no physical
relationship among the nodes;returns the locations of an element. If
not found, returns the location of last element.
•Given a target key in the ordered list, if a node in the list matches the
target value, the search returns true. If no key matches found, it
returns false.
Data Structures: A Pseudocode Approach with C
2
Data Structures: A Pseudocode Approach with C
3
List Search contd.
•Start at the beginning of the list and search until the target value is not
greater than the current node’s key. At this point the target is either less
than or equal to the current node’s key while the predecessor is pointing
to the node immediately before the current nodes.
•Test the current node and return true if the target value is equal to the
list value or false if it is less and terminate the search.
Data Structures: A Pseudocode Approach with C
4
Data Structures: A Pseudocode Approach with C
5
Retrieve Node
Retrieve node uses search node to locate the data in the list.
If the data are found, it moves the data to the output area in the calling module
and returns true.
If data are not found, returns false.
Data Structures: A Pseudocode Approach with C
6
Empty List
A simple module that returns true or false indicating that there are data in the
list or the list is empty.
Data Structures: A Pseudocode Approach with C
7
Full List
As with many other languages, C does not provide how much memory
is left in dynamic memory.
Data Structures: A Pseudocode Approach with C
8
List Count
List count returns the number of nodes in the current nodes.
Data Structures: A Pseudocode Approach with C
9
Traverse List
Traversal starts at the first node and examines each node in the succession
until the last node has been processed.
Each loop calls a process module and passes it the data and then advances the
walking pointer to the next node.
Because we need to remember where we are in the list from one call to the
next, we need to add a current position pointer to the head structure.
Each call needs to know whether it is starting from the beginning of the list or
continuing from the last node processed. This information is communicated
through the parameter list.
Data Structures: A Pseudocode Approach with C
10
Data Structures: A Pseudocode Approach with C
11
Destroy List
When the list is no longer needed and the application is not done, the list should
be destroyed.
Destroy list deletes any nodes still in the list and recycles their memory and set
the metadata to a null list condition
Data Structures: A Pseudocode Approach with C
12
Implementation
We begin with a discussion of the data structure required to
support a list. We then develop the 10 basic algorithms required
to build and use a list. In developing the insertion and deletion
algorithms, we use extensive examples to demonstrate the
analytical steps used in developing algorithms.
• Data Structure
• Algorithms
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
Data Structures: A Pseudocode Approach with C
22
Data Structures: A Pseudocode Approach with C
23
Data Structures: A Pseudocode Approach with C
24
Data Structures: A Pseudocode Approach with C
25
Data Structures: A Pseudocode Approach with C
26
Data Structures: A Pseudocode Approach with C
27
Data Structures: A Pseudocode Approach with C
28
Data Structures: A Pseudocode Approach with C
29
Data Structures: A Pseudocode Approach with C
30
Data Structures: A Pseudocode Approach with C
31
List ADT example
Data Structures: A Pseudocode Approach with C
32
Data Structures: A Pseudocode Approach with C
33
(continued)
Data Structures: A Pseudocode Approach with C
34
Data Structures: A Pseudocode Approach with C
36
Data Structures: A Pseudocode Approach with C
37
Data Structures: A Pseudocode Approach with C
38
Data Structures: A Pseudocode Approach with C
39
Data Structures: A Pseudocode Approach with C
40
Data Structures: A Pseudocode Approach with C
41
Data Structures: A Pseudocode Approach with C
42
Data Structures: A Pseudocode Approach with C
43
Data Structures: A Pseudocode Approach with C
44
Data Structures: A Pseudocode Approach with C
45
Data Structures: A Pseudocode Approach with C
46
Data Structures: A Pseudocode Approach with C
47
Data Structures: A Pseudocode Approach with C
48
Data Structures: A Pseudocode Approach with C
49
(continued)
Data Structures: A Pseudocode Approach with C
50
Data Structures: A Pseudocode Approach with C
51
Data Structures: A Pseudocode Approach with C
52