Chapter 4 Lists, Stacks and Queues

Lists

A finite, ordered sequence of data items.

Notation:

List elements have a

position

Array-Based Lists

•Insertion and deletion are Q(n).

•Prev and direct access are Q(1).

•Array must be allocated in advance.

•No overhead if all array positions are full.

Linked Lists

•Insertion and deletion are Q(1).

•Prev and direct access are Q(n).

•Space grows with number of elements.

•Every element requires overhead.

Array-based List space

D*E

D = Maximum number of elements in an array.

E = Space for data value.

Linked List space

n(P + E)

n = length of list

P = Space for pointer

E = Space for data value.

break-even point (BEP)

n = DE/(P+E)

D = Maximum number of elements in an array.

E = Space for data value.

n = length of list

P = Space for pointer

Java does not use

does not use delete explicitly to allow programmable control of memory management

System new and garbage collection

are slow

Add freelist class

support to the Link class

Freelists

freelist holds those list nodes that are not currently being used.

Stacks

Last-in-first-out (LIFO) data structure

Stack Notation

Insert: PUSH

Remove: POP

The accessible element is called TOP.

Queues

A First In First Out (FIFO) Data Structure.

Queue Notation

Insert: Enqueue

Delete: Dequeue

First element: Front

Last element: Rear

push

insert element to be the top of the stack

pop

Remove top element from the stack

enqueue

To add an item to the rear of a queue.

dequeue

To remove an item from the front of a queue.