Dynamically Linked Stacks and Queues

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<int> intlist;

.Float List

List<float> floatlist;

.Character List

List<char> 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.

9