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.

Google Online Preview   Download