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
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
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.
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.
Copyright © www.teach-ict.com