|
|
|
|
Data structures can be fixed-size such as single or double scripted arrays or dynamic that grow and shrink at execution time. Examples are Linked lists, stacks, queues, and binary trees. Creating and maintaining dynamic data structures requires dynamic memory allocation, that is the ability for a program to obtain more memory space at execution time to hold new nodes and to release space no longer required.
A linked list is a linear (sequential) collection of nodes connected by links. A program accesses it by referring to the first node, and each subsequent node via the linked reference stored in the previous node. End of the list is achieved by marking the reference to the last node as null. Linked lists are dynamic, so the length of a list can increase or decrease as necessary, unlike an array whose size is fixed. Package java.util contains class LinkedList for implementing and manipulating linked lists that grow and shrink during program execution.
Linked lists can be maintained in sorted order by inserting each new element at the proper point in the list, without moving existing link elements (unlike a stack). Linked list nodes are not stored contiguously in memory, but are contiguous logically. In a singly-linked list, each node contains reference to the next node in the list, while in the more common doubly-linked list, in addition contains a reference to the previous node.
A stack is a constrained version of a linked list, where new nodes can be added or removed only at the top. Thus it is a last-in, first-out (LIFO) data structure. The last node is at the bottom and its reference is set to null. Stacks are manipulated by push (adding a new node at the top) and pop (removing a node at the top and returning its data). The return address of the calling method is pushed onto the program execution stack to enable the method to return. If a series of method calls occur, the successive return addresses are pushed onto the stack in LIFO order so that each method can return to its caller. Stacks support recursive method calls. The program execution stack contains the memory for local variables on each invocation. When the method returns, they are popped off the stack and no longer available. Package java.util contains class Stack for implementing and manipulating stacks that grow and shrink during program execution.
A queue is similar to a checkout line in a supermarket,
the cashier services the person at the beginning of the line first, while
other customers enter at the end and wait for service. Queue nodes
are removed (dequed at the head (front) and inserted (enqued)
at the tail (end). So it is a first-in, first-out (FIFO) data structure.
Some of the uses of queues in computer systems are:
1. With a single processor, only application is serviced
at a time, while other applications are placed in a waiting queue, gradually
advancing to the front.
2. With a single printer, print jobs are spooled
where they wait in line until the printer is available.
3. Information packets wait in queues in computer
networks. Each time a packet arrives at a network node, it must be
rerouted to the next node until it reaches its final destination.
Since only one packet can be routed at a time, the other packets are enqued.
4. A file server handles file-access requests from
many clients, but having limited capacity, client requests wait in line.
For more information: Queues
A tree is a non-linear, two-dimensioned data structure with special
properties. In general tree nodes contain two or more nodes.
Binary trees nodes have exactly two nodes (none, one, or both may be null).
The root node is the first node, whose link refers to a child. The
left child is the first node in the left subtree, while the right child
is the first node in the right subtree. The children of a specific
node are called siblings. A node with no children is called a leaf
node. A node can only be inserted as a leaf node in a binary search
tree. Trees are drawn from the root node down (opposite the way trees
grow in nature).
For more information: Binary
Trees
In a binary search tree, the values in any
left subtree are less than those in the subtree's parent node, and the
values in any right subtree are greater than those in the subtree's parent
node. Binary search tree facilitates duplicate elimination.
While building a tree, the insertion operation recognizes attempts to insert
a duplicate value, because a duplicate follows the same "go left" or "go
right" decisions on each comparison as the original value did. Thus,
the insertion operation eventually compares the duplicate with a node containing
the same value, and so the insertion operation discards the duplicate value.
For more information: Binary
Search Trees
Searching a binary tree for a value that matches a key value is fast,
especially for a tightly packed tree (each level contains twice as many
elements as the previous level). A binary search tree with n elements
has a minimum of log2n levels requiring at most log2n
comparisons to find a match or to determine that no match exists.
For example searching a 1000-element binary search requires log210
or 10 comparisons since 2 10 > 1000. Searching a 1,000,000-element
tree requires 20 comparisons since 220 > 1,000,000.
There are three types of tree traversals.
In a preorder traversal, the value in each node is processed as the
node is visited. After the value in a given node is processed, the
values in the left subtree are processed, then the values in the right
subtree are processed.
In a postorder traversal, the value in each node is processed after
the values of its children
In an inorder traversal, the value of the left subtree is processed,
then the value in the node, and finally those in the right subtree.
This has the effect of processing the node values in ascending order.
For more information: Binary
Tree Traversal
Insert the following values: 39 69 94 47 50 72 55 41 97 73 in a binary search tree. Then show the preorder, inorder, and postorder traversals. Solution
Data types vs. Data Structures
A data type is a well-defined collection of data with a well-defined set of operations on it. Elementary Data Types: INTEGER, REAL, BOOLEAN, CHAR Enumerated Types: COINSIDE = {HEADS, TAIL, SIDE}
A data structure is an actual implementation of a particular abstract data type. Data structures is the manner of organizing and using information and is often used to link objects.
Example: The abstract data type Set has the operations EmptySet(S),
Insert(x,S), Delete(x,S), Intersection(S1,S2),
Union(S1,S2), MemberQ(x,S), EqualQ(S1,S2), SubsetQ(S1,S2).
Elementary Data Structures
Arrays. These let you access lots of data fast. (good) You can
have arrays of any other data type. (good)
However, you cannot make arrays bigger if your program decides it needs
more space. (bad)
Records. These let you organize non-homogeneous data into logical packages to keep everything together. (good)
These packages do not include operations, just data fields (bad, which is why we need objects)
Records do not help you process distinct items in loops (bad, which is why arrays of records are used)
Sets. These let you represent subsets of a set with such operations as intersection, union, and equivalence. (good)
Built-in sets are limited to a certain small size. (bad, but we can
build our own set data type out of arrays to solve this problem
if necessary)
Preorder Traversal: 39 69 47 41
50 55 94 72 73 97
Inorder Traversal: 39 41
47 50 55 69 72 73 94 97
Postorder Traversal: 41 55 50 47 73
72 97 94 69 39