www.gibmonks.com

Main Page




Previous Page
Next Page

[Page 1034 (continued)]

Summary

  • Dynamic data structures grow and shrink during execution.

  • Linked lists are collections of data items "lined up in a row"insertions and removals are made anywhere in a linked list.

  • Stacks are important in compilers and operating systems: Insertions and removals are made only at one end of a stackits top.

  • Queues represent waiting lines; insertions are made at the back (also referred to as the tail) of a queue and removals are made from the front (also referred to as the head).

  • Binary trees facilitate high-speed searching and sorting of data, efficient elimination of duplicate data items, representation of file system directories and compilation of expressions into machine language.

  • A self-referential class contains a pointer member that points to a class object of the same class type.

  • Self-referential class objects can be linked together to form useful data structures such as lists, queues, stacks and trees.

  • The limit for dynamic memory allocation can be as large as the amount of available physical memory in the computer or the amount of available virtual memory in a virtual memory system.

  • A linked list is a linear collection of self-referential class objects, called nodes, connected by pointer linkshence, the term "linked" list.

  • A linked list is accessed via a pointer to the first node of the list. Each subsequent node is accessed via the link-pointer member stored in the previous node.

  • Linked lists, stacks and queues are linear data structures. Trees are nonlinear data structures.

  • A linked list is appropriate when the number of data elements to be represented at one time is unpredictable.

  • Linked lists are dynamic, so the length of a list can increase or decrease as necessary.

  • A singly linked list begins with a pointer to the first node, and each node contains a pointer to the next node "in sequence."

  • A circular, singly linked list begins with a pointer to the first node, and each node contains a pointer to the next node. The "last node" does not contain a null pointer; rather, the pointer in the last node points back to the first node, thus closing the "circle."

  • A doubly linked list allows traversals both forward and backward.

  • A doubly linked list is often implemented with two "start pointers"one that points to the first element of the list to allow front-to-back traversal of the list and one that points to the last element to allow back-to-front traversal. Each node has both a forward pointer to the next node in the list in the forward direction and a backward pointer to the next node in the backward direction.

  • In a circular, doubly linked list, the forward pointer of the last node points to the first node, and the backward pointer of the first node points to the last node, thus closing the "circle."

  • A stack data structure allows nodes to be added to the stack and removed from the stack only at the top.


  • [Page 1035]
  • A stack is referred to as a last-in, first-out (LIFO) data structure.

  • The primary member functions used to manipulate a stack are push and pop. Function push inserts a new node at the top of the stack. Function pop removes a node from the top of the stack.

  • A queue is similar to a supermarket checkout linethe first person in line is serviced first, and other customers enter the line at the end and wait to be serviced.

  • Queue nodes are removed only from the head of the queue and are inserted only at the tail of the queue.

  • A queue is referred to as a first-in, first-out (FIFO) data structure. The insert and remove operations are known as enqueue and dequeue.

  • Binary trees are trees whose nodes all contain two links (none, one or both of which may be null).

  • The root node is the first node in a tree.

  • Each link in the root node refers to a child. The left child is the root node of the left subtree, and the right child is the root node of the right subtree.

  • The children of a single node are called siblings. A node with no children is called a leaf node.

  • A binary search tree (with no duplicate node values) has the characteristic that the values in any left subtree are less than the value in its parent node, and the values in any right subtree are greater than the value in its parent node.

  • A node can only be inserted as a leaf node in a binary search tree.

  • An inorder traversal of a binary tree traverses the left subtree inorder, processes the value in the root node and then traverses the right subtree inorder. The value in a node is not processed until the values in its left subtree are processed.

  • A preorder traversal processes the value in the root node, traverses the left subtree preorder, then traverses the right subtree preorder. The value in each node is processed as the node is encountered.

  • A postorder traversal traverses the left subtree postorder, traverses the right subtree postorder, then processes the value in the root node. The value in each node is not processed until the values in both its subtrees are processed.

  • The binary search tree facilitates duplicate elimination. As the tree is being created, an attempt to insert a duplicate value will be recognized and the duplicate value may be discarded.

  • The level-order traversal of a binary tree visits the nodes of the tree row by row, starting at the root node level. On each level of the tree, the nodes are visited from left to right.


Previous Page
Next Page