Transcript More Linking Up with Linked Lists

More Linking Up with
Linked Lists
Chapter 11
Nyhoff, ADTs, Data Structures and Problem Solving with C++, Second Edition, © 2005 Pearson
Education, Inc. All rights reserved. 0-13-140909-3
1
Chapter Contents
11.1 Some Variants of Singly-Linked Lists
11.2 Linked Implementation of Sparse
Polynomials
11.3 Doubly-Linked Lists and the Standard
C++ list
11.4 Case Study: Larger-Integer Arithmetic
11.5 Other Multiply-Linked Lists
Nyhoff, ADTs, Data Structures and Problem Solving with C++, Second Edition, © 2005 Pearson
Education, Inc. All rights reserved. 0-13-140909-3
2
Chapter Objectives
• Survey common variants of linked lists and why
they are used
• Study in detail an application of linked lists to
implement sparse polynomials
• Describe doubly-linked lists and how they are used
to implement C++ STL list container
• Build a class that makes it possible to do arithmetic
with large integers
• Look briefly at some other applications of multiplylinked lists
Nyhoff, ADTs, Data Structures and Problem Solving with C++, Second Edition, © 2005 Pearson
Education, Inc. All rights reserved. 0-13-140909-3
3
Linked Lists with Head Nodes
• Consider linked lists from Chapter 6
– First node is different from others
– Has no predecessor
• Thus insertions and deletions must consider
two cases
– First node or not first node
– The algorithm is different for each
Nyhoff, ADTs, Data Structures and Problem Solving with C++, Second Edition, © 2005 Pearson
Education, Inc. All rights reserved. 0-13-140909-3
4
Linked Lists with Head Nodes
• Dual algorithms can be reduced to one
– Create a "dummy" head node
– Serves as predecessor holding actual first
element
• Thus even an empty list
has a head node
Nyhoff, ADTs, Data Structures and Problem Solving with C++, Second Edition, © 2005 Pearson
Education, Inc. All rights reserved. 0-13-140909-3
5
Linked Lists with Head Nodes
• For insertion at beginning of list
– Head node is predecessor for new node
newptr->next = predptr->next;
predptr->next = newptr;
Nyhoff, ADTs, Data Structures and Problem Solving with C++, Second Edition, © 2005 Pearson
Education, Inc. All rights reserved. 0-13-140909-3
6
Linked Lists with Head Nodes
• For deleting first element from a list with a
head node
– Head node is the predecessor
predptr->next = ptr->next;
delete ptr;
Nyhoff, ADTs, Data Structures and Problem Solving with C++, Second Edition, © 2005 Pearson
Education, Inc. All rights reserved. 0-13-140909-3
7
Circular Linked Lists
• Set the link in last node to point to first node
– Each node now has both predecessor and
successor
– Insertions, deletions now easier
• Special consideration required
for insertion to empty list,
deletion from single item list
Nyhoff, ADTs, Data Structures and Problem Solving with C++, Second Edition, © 2005 Pearson
Education, Inc. All rights reserved. 0-13-140909-3
8
Circular Linked Lists
• Traversal algorithm must be adjusted
if (first != 0) // list not empty
{
ptr = first;
do
{
// process ptr->data
ptr = ptr->next;
}
while (ptr != first);
}
• A do-while loop must be used instead of a
while loop
– Why is this required?
Nyhoff, ADTs, Data Structures and Problem Solving with C++, Second Edition, © 2005 Pearson
Education, Inc. All rights reserved. 0-13-140909-3
9
Linked Implementation of
Sparse Polynomials
• Consider a polynomial of degree n
– Can be represented by a list
• For a sparse polynomial this is not efficient
Nyhoff, ADTs, Data Structures and Problem Solving with C++, Second Edition, © 2005 Pearson
Education, Inc. All rights reserved. 0-13-140909-3
10
Linked Implementation of
Sparse Polynomials
• We could represent a polynomial by a list of
ordered pairs
– { (coef, exponent) … }
• Fixed capacity of
array still problematic
– Wasted space for
sparse polynomial
Nyhoff, ADTs, Data Structures and Problem Solving with C++, Second Edition, © 2005 Pearson
Education, Inc. All rights reserved. 0-13-140909-3
11
Linked Implementation of
Sparse Polynomials
• Linked list of these ordered pairs provides an
appropriate solution
– Each node has form shown
• Now whether sparse or well populated, the
polynomial is represented efficiently
Nyhoff, ADTs, Data Structures and Problem Solving with C++, Second Edition, © 2005 Pearson
Education, Inc. All rights reserved. 0-13-140909-3
12
Linked Implementation of
Sparse Polynomials
• Note start of Polynomial class template
– Type parameter CoefType
– Term and Node are inner classes
• Addition operator
– Adds coefficients of like degrees
– Must traverse the two addend polynomials
– Requires temporary pointers for each polynomial
(the addends and the resulting sum)
Nyhoff, ADTs, Data Structures and Problem Solving with C++, Second Edition, © 2005 Pearson
Education, Inc. All rights reserved. 0-13-140909-3
13
Addition Operator
• Requires temporary pointers for each
polynomial (the addends and the resulting
sum)
Nyhoff, ADTs, Data Structures and Problem Solving with C++, Second Edition, © 2005 Pearson
Education, Inc. All rights reserved. 0-13-140909-3
14
Addition Operator
• As traversal takes place
– Compare exponents
– If different, node with smaller exponent and its coefficient
attached to result polynomial
– If exponents same, coefficients added, new
corresponding node attached to result polynomial
View source
code
Nyhoff, ADTs, Data Structures and Problem Solving with C++, Second Edition, © 2005 Pearson
Education, Inc. All rights reserved. 0-13-140909-3
15
Doubly-Linked Lists
• Bidirectional lists
– Nodes have data part,
forward and backward link
• Facilitates both forward and backward
traversal
– Requires pointers to both first and last nodes
Nyhoff, ADTs, Data Structures and Problem Solving with C++, Second Edition, © 2005 Pearson
Education, Inc. All rights reserved. 0-13-140909-3
16
Doubly-Linked Lists
• To insert a new node
– Set forward and backward links to point to
predecessor and successor
– Then reset forward link of predecessor,
backward link of successor
Nyhoff, ADTs, Data Structures and Problem Solving with C++, Second Edition, © 2005 Pearson
Education, Inc. All rights reserved. 0-13-140909-3
17
Doubly-Linked Lists
• To delete a node
– Reset forward link of predecessor, backward link
of successor
– Then delete removed node
Nyhoff, ADTs, Data Structures and Problem Solving with C++, Second Edition, © 2005 Pearson
Education, Inc. All rights reserved. 0-13-140909-3
18
The STL list<T> Class Template
• A sequential container
– Optimized for insertion and erasure at arbitrary
points in the sequence.
– Implemented as a circular doubly-linked list with
head node.
Nyhoff, ADTs, Data Structures and Problem Solving with C++, Second Edition, © 2005 Pearson
Education, Inc. All rights reserved. 0-13-140909-3
19
Comparing List<t> With Other Containers
Property
Array
vector<T> deque<T> list<T>
Direct/random access ([])
+ (exclnt) +
 (good)
X
Sequential access
+
+

+
Insert/delete at front
-(poor)
-
+
+
Insert/delete at end
+
+
+
+
Insert/delete in middle
-
-
-
+
Overhead
lowest
low
low/medium
high
• Note : list<T> does not support direct access
– does not have the subscript operator [ ].
Nyhoff, ADTs, Data Structures and Problem Solving with C++, Second Edition, © 2005 Pearson
Education, Inc. All rights reserved. 0-13-140909-3
20
list<t> Iterators
• list<T>'s iterator is "weaker" than that for
vector<T>.
 vector<T>:
random access iterators
 list<T>:
bidirectional iterators
• Operations in common
 ++
Move iterator to next element
(like ptr = ptr-> next)
 --
Move iterator to preceding element
(like ptr = ptr-> prev)
 *
dereferencing operator
(like ptr-> data)
Nyhoff, ADTs, Data Structures and Problem Solving with C++, Second Edition, © 2005 Pearson
Education, Inc. All rights reserved. 0-13-140909-3
21
list<t> Iterators
• Operators in common
=
assignment
(for same type iterators)
it1 = it2 makes it1 positioned at
same element as it2
 == and !=
(for same type iterators)
checks whether iterators are positioned at
the same element
 See basic list operations,
Table 11-2, pg 621
 View demonstration of list operations, Fig. 11-1
Nyhoff, ADTs, Data Structures and Problem Solving with C++, Second Edition, © 2005 Pearson
Education, Inc. All rights reserved. 0-13-140909-3
22
Example: Internet Addresses
• Consider a program that stores IP addresses
of users who make a connection with a
certain computer
– We store the connections in an
AddressCounter object
– Tracks unique IP addresses and how many
times that IP connected
• View source code, Fig. 11.2
– Note uses of STL list and operators
Nyhoff, ADTs, Data Structures and Problem Solving with C++, Second Edition, © 2005 Pearson
Education, Inc. All rights reserved. 0-13-140909-3
23
The STL list<T> Class Template
Node structure
struct list_node
{ pointer next,
prev;
T data;
}
Nyhoff, ADTs, Data Structures and Problem Solving with C++, Second Edition, © 2005 Pearson
Education, Inc. All rights reserved. 0-13-140909-3
24
The STL list<T> Class Template
• But it's allo/deallo-cation scheme is complex
– Does not simply using new and delete
operations.
• Using the heap manager is inefficient for
large numbers of allo/deallo-cations
– Thus it does it's own memory management.
Nyhoff, ADTs, Data Structures and Problem Solving with C++, Second Edition, © 2005 Pearson
Education, Inc. All rights reserved. 0-13-140909-3
25
The STL list<T> Memory Management
When a node is allocated
1. If there is a node on the free list, allocate it.
•
This is maintained as a linked stack
2. If the free list is empty:
a) Call the heap manager to allocate a block of
memory (a "buffer", typically 4K)
b) Carve it up into pieces of size required for a
node of a list<T>.
Nyhoff, ADTs, Data Structures and Problem Solving with C++, Second Edition, © 2005 Pearson
Education, Inc. All rights reserved. 0-13-140909-3
26
The STL list<T> Memory Management
• When a node is deallocated
– Push it onto the free list.
• When all lists of this type T have been
destroyed
– Return it to the heap
Nyhoff, ADTs, Data Structures and Problem Solving with C++, Second Edition, © 2005 Pearson
Education, Inc. All rights reserved. 0-13-140909-3
27
Case Study: Large-Integer
Arithmetic
• Recall that numeric representation of
numbers in computer memory places limits
on their size
– 32 bit integers, two's complement max
2147483647
• We will design a BigInt class
– Process integers of any size
– For simplicity, nonnegative integers only
Nyhoff, ADTs, Data Structures and Problem Solving with C++, Second Edition, © 2005 Pearson
Education, Inc. All rights reserved. 0-13-140909-3
28
BigInt Design
• First step : select a storage structure
– We choose a linked list
– Each node sores a block of up to 3 consecutive
digits
– Doubly linked list for traversing in both directions
Nyhoff, ADTs, Data Structures and Problem Solving with C++, Second Edition, © 2005 Pearson
Education, Inc. All rights reserved. 0-13-140909-3
29
BigInt Design
• Input in blocks of 3 integers, separated by
spaces
– As each new block entered, node added at end
• Output is traversal, left to right
Nyhoff, ADTs, Data Structures and Problem Solving with C++, Second Edition, © 2005 Pearson
Education, Inc. All rights reserved. 0-13-140909-3
30
BigInt Design
• Addition adds the groupings right to left
– Keeping track of carry digits
Nyhoff, ADTs, Data Structures and Problem Solving with C++, Second Edition, © 2005 Pearson
Education, Inc. All rights reserved. 0-13-140909-3
31
BigInt Implementation
• Standard list type provides all the tools we
need
• Note class declaration, Fig. 11.3A
• View class definition, Fig. 11.3B
• Driver program to demonstrate use of the
class, Fig 11.4
Nyhoff, ADTs, Data Structures and Problem Solving with C++, Second Edition, © 2005 Pearson
Education, Inc. All rights reserved. 0-13-140909-3
32
Multiply-Ordered Lists
• Ordered linked list
– Nodes arranged so data items are in
ascending/descending order
• Straightforward when based on one data
field
– However, sometimes necessary to maintain links
with a different ordering
• Possible solution
– Separate ordered linked lists – but wastes space
Nyhoff, ADTs, Data Structures and Problem Solving with C++, Second Edition, © 2005 Pearson
Education, Inc. All rights reserved. 0-13-140909-3
33
Multiply-Ordered Lists
• Better approach
– Single list
– Multiple links
Nyhoff, ADTs, Data Structures and Problem Solving with C++, Second Edition, © 2005 Pearson
Education, Inc. All rights reserved. 0-13-140909-3
34
Sparse Matrices
• Usual storage is 2D array or 2D vector
• If only a few nonzero entries
– Can waste space
• Stored more efficiently with linked structure
– Similar to sparse polynomials
– Each row is a linked list
– Store only nonzero entries for the row
Nyhoff, ADTs, Data Structures and Problem Solving with C++, Second Edition, © 2005 Pearson
Education, Inc. All rights reserved. 0-13-140909-3
35
Sparse Matrices
• For
A=
we represent with
Nyhoff, ADTs, Data Structures and Problem Solving with C++, Second Edition, © 2005 Pearson
Education, Inc. All rights reserved. 0-13-140909-3
36
Sparse Matrices
• This still may waste space
– Consider if many rows were all zeros
• Alternative implementation
– Single linked list
– Each node has row, column,
entry, link
• Resulting list
Nyhoff, ADTs, Data Structures and Problem Solving with C++, Second Edition, © 2005 Pearson
Education, Inc. All rights reserved. 0-13-140909-3
37
Sparse Matrices
• However … this loses direct access to rows
• Could replace array of pointers with
– Linked list of row head nodes
– Each contains pointer to non empty row list
Nyhoff, ADTs, Data Structures and Problem Solving with C++, Second Edition, © 2005 Pearson
Education, Inc. All rights reserved. 0-13-140909-3
38
Sparse Matrices
• If columnwise processing is desired
– Use orthogonal list
– Each node stores row, column, value, pointer to
row successor, pointer to column successor
Nyhoff, ADTs, Data Structures and Problem Solving with C++, Second Edition, © 2005 Pearson
Education, Inc. All rights reserved. 0-13-140909-3
39
Sparse Matrices
• Note the resulting
representation of
the matrix
A=
Nyhoff, ADTs, Data Structures and Problem Solving with C++, Second Edition, © 2005 Pearson
Education, Inc. All rights reserved. 0-13-140909-3
40
Generalized Lists
• Examples so far have had atomic elements
– The nodes are not themselves lists
• Consider a linked list of strings
– The strings themselves can be linked lists of
characters
This is an
example of a
generalized list
Nyhoff, ADTs, Data Structures and Problem Solving with C++, Second Edition, © 2005 Pearson
Education, Inc. All rights reserved. 0-13-140909-3
41
Generalized Lists
• Commonly represented as linked lists where
– Nodes have a tag field along with data and link
• Tag used to indicate whether data field holds
– Atom
– Pointer
to a list
Nyhoff, ADTs, Data Structures and Problem Solving with C++, Second Edition, © 2005 Pearson
Education, Inc. All rights reserved. 0-13-140909-3
42
Generalized Lists
• Lists can be
shared
– To represent
(2, (4,6), (4,6))
• For polynomials in two variables
P(x,y) = 3 + 7x + 14y2 + 25y7 – 7x2y7 + 18x6y7
Nyhoff, ADTs, Data Structures and Problem Solving with C++, Second Edition, © 2005 Pearson
Education, Inc. All rights reserved. 0-13-140909-3
43