Transcript Linear Linked Structures Part 1

COSC 1P03
Linear Linked Structures
A bank is a place where they lend you an umbrella
in fair weather and ask for it back when it begins to
rain.
Robert Frost (1874-1963)
Data Structures and Abstraction
5.1
COSC 1P03
Dynamic Structures
 collections
 limitations of static structures (i.e. arrays)
 fixed size
 waste space
 rearrangement of entries
 sharing between structures?
 dynamic data structures
 change size over time
 storage proportional to amount of information
 linked structures
 nodes (objects) connected together by references
 dynamic allocation/deallocation
 in array proximity implicit, in linked structure it is explicit
 linear linked structures
 aka linked lists
Data Structures and Abstraction
5.2
COSC 1P03
Sequentially-linked Structures





each node indicates its successor (via a reference)
first node located via reference
last node has no successor (null)
each node represents one entity
empty collection has null reference
Data Structures and Abstraction
5.3
COSC 1P03
Representation
 nodes are objects
 dynamic creation
 let entity objects be nodes?
 add reference field
 disadvantages
 object must “know” it is on list
 multiple lists
 must modify class
Data Structures and Abstraction
5.4
COSC 1P03
Node Wrapper Class
 separate class references objects
 wrapper class, mixin
 fields
 reference (p.theStudent)
 link (p.next)
 constructor
 visibility
 class
 fields
 as sequentially-linked structure
 general case
 initial (empty) state
 multiple lists
 different sequence of Nodes, same objects
Data Structures and Abstraction
5.5
COSC 1P03
Operations
 insertion
 where?
 deletion
 which node?
 traversal
 “visit” all nodes
 like array traversal
 search
 special traversal
 simple vs exhaustive
Data Structures and Abstraction
5.6
COSC 1P03
Insertion
 insert where?
 front
 end
 in some order (e.g. sorted)
 at front
 new entry points to previous front
 list reference points to new entry
 pattern
 O(1)
 repeated application
 reverse order
Data Structures and Abstraction
5.7
COSC 1P03
Deletion
 delete which node?
 first
 last
 matching a key
 only if not empty
 delete first
 move list pointer to second node
 garbage collection
 node
 entity
 pattern
 O(1)
Data Structures and Abstraction
5.8
COSC 1P03
Traversal
 sequential processing
 to get to nth node must first get to (n-1)st node
 travelling pointer
 start at first node
 move to node's successor
 p = p.next
 termination
 no more nodes (p == null)
 pattern
 O(n)
 vs array traversal
 sequential traversal pattern
Data Structures and Abstraction
5.9
COSC 1P03
Search
 search key
 two outcomes
 success
 failure
 variant of traversal
 two exits
 end of list
 found item
 pattern
 O(n)
Data Structures and Abstraction
5.10
COSC 1P03
Insertion at End of List
 for insertion in order
 find end of list
 traversal
 2 travelling pointers
 initial state
 q is predecessor of p
 insert
 pattern
 traverse
 updating p & q
 insert
 2 cases
 q == null (empty list)
 q != null (at end)
 O(n)
Data Structures and Abstraction
5.11
COSC 1P03
Deletion of Last Node
 must modify second last node
 find second last node
 traversal
 2 travelling pointers
 test
 pattern
 pre test
 error
 traverse
 delete
 2 cases
 q == null (only node)
 q != null (last node)
 O(n)
Data Structures and Abstraction
5.12
COSC 1P03
The End
Data Structures and Abstraction
5.33