19. Summary

The Linked List

Use: Good for holding data in an ordered manner

Feature: Can insert and remove any item (node) from the list

Pointers: Every node has a pointer locating the next node. The last node has a null pointer

Disadvantage: Complicated maintenance of pointers, if all you want is do is to read either the last or first item (node).

Advantage: The most flexible type of linear list

The Stack

Use: Widely use to control program execution of subroutines

Feature: Last-in First out (LIFO) means that only the last item is accessible to the programmer.

Pointers: Only one pointer used, called the stack pointer. It locates the last item in the stack

Disadvantage: Stack overflow and Stack underflow can cause program crash

Advantage: Easy to ensure that items are removed (read) in reverse order

The Queue

Use: Anywhere where resources have to be shared, such as a print queue

Feature: First-in, First-out (FIFO) means that only the first item can be removed (read). Items are added to the back of the queue. The nodes in-between cannot be accessed by the programmer

Pointers: Maintains 2 pointers. One locating the front of the queue, the other locating the back of the queue

Disadvantage: Not as flexible as a general list as only the front of the queue can be read

Advantage: Easy to ensure that items are removed (read) in the order they were entered

The Circular Queue (circular buffer)

Use: Excellent for passing data from one process to another

Feature: Still a First-in, First-Out data structure, like the standard queue but as items are read from the front of the queue, items are added to the rear the queue. Read and Write normally carried out by different processes.

Pointers: Maintains 2 pointers like a standard queue

Disadvantage: Buffer underflow (i.e. empty) can be a problem. The Read and Write processes have to be carefully managed to avoid this.

Advantage: The size of the buffer should be well-defined at the design stage and so can be set for maximum memory efficiency when moving data from one process to another.

The Tree

Use: Excellent for storing, manipulating and searching data records

Features: The tree maintains the relationship between data items in a parent-child-sibling manner.

Pointers: Many, as each node in the tree has to locate its parent, sibling and child nodes

Disadvantage: Over-complicated for maintaining unrelated data items

Advantage: Easy to maintain the relationship between data items

The Binary Tree

Use: Excellent for maintaining sorted and related data items

Features: The parent node in a binary tree only ever has two child nodes, the LEFT and the RIGHT child nodes. The binary tree rule is that all items before the parent is located in the left sub-tree and all items later than the parent is located in the right sub-tree.

Pointers: Many. Each node locates its parent and location of its left and right child nodes (if any)

Advantage: The binary structure and rule makes it simple to add, delete and sort related data items

Disadvantage: Not as flexible as the general tree structure. Over-complicated for maintaining unrelated data items.