meljun cortes lists rm104tr-7

7/29/2019 MELJUN CORTES LISTS Rm104tr-7

1/15

Lesson 7 - 1

Year 1

CS113/0401/v1

A record consists of different data

items stored in an array

Below is a list consisting of four

data items that are not linked

An example is given below

Inv. No Cust. No. Date Inv. No

Rec. 1 Rec. 1 Rec. 1Rec. 1

Four lists which must stay linked

LESSON 7 LISTS


2/15


3/15

Lesson 7 - 3

Year 1

CS113/0401/v1

Nameor

Start

Nextpointer field

Information part

LINKED LISTS

A linked list, or one-way list, is a linear

collection of data elements, called

nodes, where the linear order is given bymeans of pointers, That is, each node is

divided into two parts: the first part

contains the information of the element,

and the second part, called the li9nk

field or nextpointer field, contains the

address of the next node in the list.

Example : Linked list with 3 nodes


4/15

Lesson 7 - 4

Year 1

CS113/0401/v1

Inv. No Cust. No. Date Inv. No

Rec. 1

Rec. 1

Rec. 1

Rec. 1

Two way pointer

The lists after ordering

LINKED LIST

A more useful application of a list is a

linked list

The Invoice Number, Customer Number,Date and Amount are linked by a two

way pointer


5/15

Lesson 7 - 5

Year 1

CS113/0401/v1

Example (Part c; Question 4/91)

A LINKED TABLE holding KEY

numerical values in ASCENDING orderof which the POINTER LISTSTART

holds the value 2, contains

i. Re-write the table as it would appear if

we added, at INDEX 4 THE KEY 95

and KEY 110 at INDEX 5.

[4]

ii. Show the original table as it would

appear if KEY 96 were DELETED.

[2]

LISTSTART

2 Index Key Link to Next Record1 96 3

2 84 1

3 106 -1

EXERCISE


6/15

Lesson 7 - 6

Year 1

CS113/0401/v1

2 Index Key Link to Next Record

1 96 3

2 84 53 106 5

4 95 1

5 110 -1

EXERCISE

Solution for part c(i);

Solution for part c(ii) (to be solvein class)


7/15

Lesson 7 - 7

Year 1

CS113/0401/v1

PROCESS PROGRAM S/ROUTINE

Spool

:Line n

:

Line 1

S/R call

Line n;

:

:

Line 1

Program Lists with pointers

SYSTEM LISTS

Program location in main memory

and its control during executionby linked list for example calling

of subroutines by main programs

By managing pointers locations,

the economy of storage and

speed of execution are achieved


8/15

Lesson 7 - 8

Year 1

CS113/0401/v1

QUEUES

It is a FIFO (First-In-First-Out)structures which means that the

first item to enter the queue is the

first to leave and new items

always get added to the end of

the queue.

As with the stack we can

represent a queue by a one-

dimensional array with the need

for two pointers. The first toindicate the front of the queue

and the other indicate the next

apace capable of holding an

element joining the queue, these

being the head and tail pointersrespectively.


9/15

Lesson 7 - 9

Year 1

CS113/0401/v1

A method of inserting and retrieving data

similar to a stack but onFIRST-IN-

FIRST-OUT

The queue operation is awkward

because the elements are pushed to thefront and new elements are added from

the bottom, sometimes referred to as a

PUSHUP STAQCK or LIST

Other types of queues can be the

DEQUE (or DOUBLE-ended-Queue)and the WRAP-AROUND-STACK

Head

Pointer1

2

3

4

5

6

7

8

1

2

3

Tail

Pointer

1. POP

2. LIST

3. PUSH

QUEUE


10/15

Lesson 7 - 10

Year 1

CS113/0401/v1

DEQUE

Data are push and pop (add and

delete) from both ends

WRAP-AROUND-STACK

In this type the tail pointer cannot

be push out but moves in a

circular manner ahead of the

head pointer


11/15

Lesson 7 - 11

Year 1

CS113/0401/v1

STACKS

The main characteristics of a stack

is that it is a LIFO (Last-In-First-Out)structure. It can be liken to a pile of

plates in which it is easy (if someone

a little unstable ) to add extra plates

to the top. Plates can also be easily

removed from the top of the pile, butnot by extrication from the bottom of

the pile.

We can represent a stock as a one-

dimensional array with two pointers,

one pointer to the base of the stack (

to identify the first elements ) and

the other pointing position of the first

available element, this being called

the stack pointer.


12/15

Lesson 7 - 12

Year 1

CS113/0401/v1

Head pointer

Base pointer

7

6

5

4

3

2

1 8

8

7

6

5

4

3

2

1 3

Pop

Head pointer

Base pointer

Push

Push and Pop operation

STACKS

Stack works on LAST-IN-FIRST-

OUT The elements are addedfrom the top termed as PUSH

and removed from the top termed

POP.

The HEAD and TAIL pointers are

used to control.


13/15

Lesson 7 - 13

Year 1

CS113/0401/v1

STACKS

An example of stack operation

10 DIM S(50)

80 REM **PUSHING

SEQUENCE**

90 IF P


14/15

Lesson 7 - 14

Year 1

CS113/0401/v1

Exercise

NCC JUNE 92 Q6.

A. A circular QUEUE of characters is

stored in RAM locations 500 t6o 509inclusive. At the start the queue is

empty and both Front and Back

pointers set to 500. The BACK

pointer is incremented as items are

added.

i. Show the queue and pointers after

performing each of the following

steps:

ADD the characters A, B, C, D in

order: Remove THREE

characters:

ADD the characters E, F, G, H, I:Remove ALL characters


15/15

Lesson 7 - 15

Year 1

CS113/0401/v1

EXERCISE

NCC JUNE 92 Q6.

ii. How many characters can be stored

in the queue? [1]

iii. Describe briefly how we know thequeue is full [3]

iv. Why is the stack CIRCULAR?

[1]

v. State two uses of queues

[2]

meljun cortes lists rm104tr-7

Documents