Linked Lists
Linked Lists
Pointers
Singly Linked Lists
Dynamically Linked Stacks and Queues
Polynomials
Additional List Operations
Equivalence Relations
Sparse Matrices
Doubly Linked Lists
Generalized Lists
Pointers
Sequential representation
Disadvantages
Insertion & Deletion
Varying size
Linked representation
Singly/Doubly linked lists
Singly Linked Lists
Linked list
An ordered sequence of nodes with links
The nodes do not reside in sequential locations
The locations of the nodes may change on different runs
Linked list may be represented in mmemory: Data[ ], Link[ ]
Singly Linked Lists(Cont.)
Insertion
Singly Linked Lists (Cont.)
Deletion
Create and Use Linked Lists in C++
.Node Class
class ListNode{
friend class List;
private:
int data; //char data[3]
ListNode *Link;
};
.List Class
class List {
public:
//List manipulation operations
void create();
void insert();
void delete();
private:
ListNode *first;
};
.Creating a two-node list
//Program 4.3, example 4.2, page 172.
.ListNode constructor
//Program 4.3, example 4.2, page 172.
.Inserting a node
//Program 4.4, figure 4.11, example 4.3, page 173.
.Deleting a node
//Program 4.5, example 4.4, page 174.
Implementing Linked Lists with Templates
.Integer List
List intlist;
.Float List
List floatlist;
.Character List
List charlist;
.Template definition of linked lists
//Program 4.6, page 176.
Circular Lists
Circular list: the link field of the last node points to the first
//Figure 4.13, page 184.
. The empty circular lists
//Figure 4.16, page 185.
Linked Stacks and Queues
.When we need multiple stacks and queues, linked stacks and linked queues are good solution.
A Representation of m Stacks
.A collection of m stacks
Stack *stack = new Stack[m];
.Stack class definition and adding a node and deleting top node
//program 4.15, program 4.16, program 4.17, page 188.
Polynomials
Polynomial representation
.Polynomial class definition and declaration of operator+( )
//program 4.20, page 191
. Implementation of operator+( )
//program 4.21, page 193
Example
a= 3x14+ 2x8+ 1
b= 8x14- 3x10+ 10x6
//figure 4.18: Polynomial representation, page 191.
//figure 4.19: Polynomial adding, C= a + b, page 192.
Additional List Operations
Reversing a chain
• Concatenates two chain
Circular Lists Representation of Polynomials
Representing polynomials
Nonezero polynomials: 3x14 + 2x8 + 1
Sparse Matrices
.Head field: to distinguish between head node and element node(false).
.The Head node for row i is also the head node for column i.
(a) head node (b) typical node
.Example:
Doubly Linked Lists
.If we have a problem in which moving in either direction is often necessary, then it is useful to have doubly linked lists.
Insertion into a Doubly Linked Circular List
.Program 4.35, page 219.
Deletion from a Doubly Linked Circular List
.Program 4.34, figure 4.31, page 219.
Generalized Lists
Generalized List
A generalized list, A, is a finite sequence of n>= 0 elements, a0,…,an-1, where ai is either an atom or a list.
Examples
D=()
A= (a, (b, c))
B= (A, A, ())
C= (a, C)
Consequences
lists may be shared by other lists (Example B)
lists may be recursive(Example C)
Generalized Lists(Cont.)
Represent polynomial
p(x,y,z)= x10y3z2+2x8y3z2+3x8y2z2+x4y4z+6x3y4z+2yz
Solution I
-
Solution II
Using general list
3x2y: See Figure 4.32, p233.
Summary
Lists
Singly/Doubly linked list
Circular
Singly/Doubly linked list
Linked lists with head
Generalized linked lists
Operations
Insertion, Deletion, Modification, Retrieval, Concatenation, etc.
-----------------------
null
vat
sat
cat
bat
vat
bat
cat
sat
0
4
1
1
2
2
3
4
5
6
vat
null
sat
cat
bat
first
Insert mat after cat
mat
null
vat
sat
cat
bat
first
Delete mat from list
mat
null
vat
sat
cat
bat
null
(a)Linked Stack
data link
top
null
data link
rear
(b)Linked Queue
front
coef expon link
0
1
8
2
14
3
head
down
down
right
col
row
head
value
right
next
Note: The tag field of a node is not shown;
0 2
11
2 1
-4
1 0
12
H3
H2
H1
H0
Insert
Coef expx expy
expz link
first
H3
H2
H1
H0
Head node
rlink
llink
Doubly linked circular list with head node
4 4
3 3
-15
0 0 11 0
12 0 0 0
0 -4 0 0
0 0 0 -15
................
................
In order to avoid copyright disputes, this page is only a partial summary.
To fulfill the demand for quickly locating and searching documents.
It is intelligent file search solution for home and business.