Linked List Based ADTs
- Stacks
- Linked implementation overcomes the set maximal size of the
array implementation.
- Direct implementation
(HSM Ch.4.5)
- Use a singly linked list (HSM Fig.4.17, Prog.4.15)
- Push and pop at the head of the list (HSM Prog.4.16-17)
- Stack is empty if the linked list is empty, and is "never"
full
- Using the doubly linked list class in
linkedlistclass.h and
linkedlistclass.cpp
- Inheriting from the doubly linked list class is also possible
- Queues
(HSM Ch.4.5)
- Direct implementation
- Use a singly linked list (HSM Fig.4.17)
- Enqueue at the end of the list (rear of the queue), and
dequeue at the head (front of the queue) (HSM Prog.4.18-19)
- Queue is empty if the linked list is empty, and is "never"
full
- Using or inherting from the doubly linked list class are
also possible
- Polynomials
(HSM Ch.4.6)
- Represent as a linked list of terms
(HSM Ch.4.6.1, Fig.4.18, Prog.4.20)
- No limit to number of terms
- No unused terms - good for sparse polynomials in particular
- Adding polynomials
- How it's done
(HSM Ch.4.6.2)
- Complexity for polynomials with M and N terms
- Addition of coeeficients O(min(M,N))
- Exponent comparisons O(M+N)
- Creation of nodes O(M+N)
- O(M+N), and since every term must be examined at least
once, this is optimal, i.e., Theta(M+N).
- Equivalence classes
(HSM Ch.4.7)
- What are they?
- The equivalence relation
- Reflexivity, symmetry, transitivity
- Examples: equality, friendship, connectivity
- Computing equivalence classes linearly, for N objects and M
equivalence relations
- Stacking nodes to be processed
- Complexity
- Initialization of seq and out is O(N)
- Processing input relations is O(M)
- Outputing classes looks at each object and each node,
which is O(N+M).
- Overall O(N+M), and as each object and relation must
be visited when creating classes, Theta(N+M)
- EquivalenceClass.cpp
- Doing it recursively
- Recursion holds current node while transivitity is followed
- Sparse Matrices
(HSM Ch.4.8)
- Linked implementation overcomes the problem of inserting nodes
at run time during operations such as addition and multiplication
when using an
array implementation.
- Representation
(HSM Ch.4.8.1)
- Matrix nodes contain row and column index, value, and links
to the next/previous nodes in row and column
- Linked list of row/column head nodes, with first and last
pointers to the first and last matrix nodes in the row/column
- Matrix head node with pointers to first and last row and
column head nodes.
- HSM Program 4.30 provides an optimized version
- Sparse matrix input for an N x M matrix with R non-zero nodes
(HSM Ch.4.8.2)
- Use an extra array to point to head nodes while inputing
- Complexity
- Head nodes set up in O(max(N,M))
- Matrix nodes are set up in O(R) time, due to linked
structure giving O(1) to put in a node
- Completing the linking takes O(max(N,M))
- Overall O(max(N+M) + R) = O(N+M+R)
- Priority Queues
(HSM Ch.5.6.1)
- Examples (HSM p.284)
- Abstract class
- Linked list representation
- Ordered or unordered
- Insertion and deletion complexity
Exercises
- Linked queues: Implement a queue class by using the doubly linked
list class in
linkedlistclass.h and
linkedlistclass.cpp.
- Circular polynomials: HSM Ch.4.6, exercise 4.
- Operations on,linked sparse matrices: HSM Ch.4.8, exercises 1, 4.
Lab Tasks
Exam Style Questions
- Describe how a {stack,queue} can be represented using a linked list?
What is the main advantage of this representation over arrays?
- Describe how a polynomial may be represented using a linked list.
What is the main advantage of this representation over arrays?
- Give an algorithm for adding two polynomials represented using
linked lists.
- Below is the algorithm for adding two polynomials represented using
linked lists.
[Pretend the algorithm is written out here]
Derive, using using step counts or reasonable explanation, the
asymptotic complexity of this algorithm.
- Define an equivalence class.
- Describe how linked lists may be used in an algorithm to determine
equivalence classes from a sequence of equivalence pairs.
- Describe how a sparse matrix may be represented using linked lists.