Data Structures
Fixed-sized data structures such as single and double-subscripted arrays do not grow or shrink, where as dynamic data structures can grow and shrink at execution time. There are a number of dynamic data structures that grow and shrink
| Linked Lists | are collections of data items "lined up in a row", insertions and deletions can be made anywhere in the linked list |
| Stacks | are used in compilers and operating systems, insertions and deletions are made only at one end of the stack - its top. |
| Queues | represent waiting lines, insertion are made at the back (known as the tail) and deletions are made at the front (known as the head) of the queue |
| Trees | facilitate high-speed searching and sorting of data, efficent elimination of duplicate data items, representing file system directories and compiling expressions into machine language |
I have touched on Collections before, so you may want to take a peek.
A self-referential class contains a reference member that refers to a class object of the same class type
| example | class Node { private int data; public Node( int data){ ... }; // constructor public void setNext( Node nextNode){ ... }; // method body public Node getNext(){ ... }; // method body } |
Self-referential objects can be linked together to form useful data structures such as lists, queues, stacks and trees.
Java programs do not release dynamically allocated memory, Java performs automatic garbage collection. The limit for dynamic memory allocation can be as large as the amount of available physical memory and available disk space in a virtual-memory system.
See Garbage collection for more details on how Java gets back the memory that is no longer used.
A linked list is a linear collection of self-referential class objects, called nodes, connected by reference links -hence, the term linked lists.
**** linked list picture ****
A linked list is accessed by the first node in the list, each subsequent node is accessed via the link-reference member stored in the previous node, the last nodes reference is set to null. Linked lists are dynamic so they can increase or decrease in size. You can keep the linked list on sorted oreder as additional nodes can be placed anywhere in the structure, however the nodes may not be held in a contiguous piece of memory and may well be scattered.
| Linked List example | // ListNode Class
class ListNode {
// package access data so class List can access it directly
Object data;
ListNode next;
// Constructor: Create a ListNode that refers to Object o.
ListNode( Object o ) { this( o, null ); }
// Constructor: Create a ListNode that refers to Object o and
// to the next ListNode in the List.
ListNode( Object o, ListNode nextNode )
{
data = o; // this node refers to Object o
next = nextNode; // set next to refer to next
}
// Return a reference to the Object in this node
Object getObject() { return data; }
// Return the next node
ListNode getNext() { return next; }
}
// Class List definition
public class List {
private ListNode firstNode;
private ListNode lastNode;
private String name; // String like "list" used in printing
// Constructor: Construct an empty List with s as the name
public List( String s )
{
name = s;
firstNode = lastNode = null;
}
// Constructor: Construct an empty List with
// "list" as the name
public List() { this( "list" ); }
// Insert an Object at the front of the List
// If List is empty, firstNode and lastNode will refer to
// the same object. Otherwise, firstNode refers to new node.
public synchronized void insertAtFront( Object insertItem )
{
if ( isEmpty() )
firstNode = lastNode = new ListNode( insertItem );
else
firstNode = new ListNode( insertItem, firstNode );
}
// Insert an Object at the end of the List
// If List is empty, firstNode and lastNode will refer to
// the same Object. Otherwise, lastNode's next instance
// variable refers to new node.
public synchronized void insertAtBack( Object insertItem )
{
if ( isEmpty() )
firstNode = lastNode = new ListNode( insertItem );
else
lastNode = lastNode.next = new ListNode( insertItem );
}
// Remove the first node from the List.
public synchronized Object removeFromFront()
throws EmptyListException
{
Object removeItem = null;
if ( isEmpty() )
throw new EmptyListException( name );
removeItem = firstNode.data; // retrieve the data
// reset the firstNode and lastNode references
if ( firstNode.equals( lastNode ) )
firstNode = lastNode = null;
else
firstNode = firstNode.next;
return removeItem;
}
// Remove the last node from the List.
public synchronized Object removeFromBack()
throws EmptyListException
{
Object removeItem = null;
if ( isEmpty() )
throw new EmptyListException( name );
removeItem = lastNode.data; // retrieve the data
// reset the firstNode and lastNode references
if ( firstNode.equals( lastNode ) )
firstNode = lastNode = null;
else {
ListNode current = firstNode;
while ( current.next != lastNode ) // not last node
current = current.next; // move to next node
lastNode = current;
current.next = null;
}
return removeItem;
}
// Return true if the List is empty
public synchronized boolean isEmpty()
{ return firstNode == null; }
// Output the List contents
public synchronized void print()
{
if ( isEmpty() ) {
System.out.println( "Empty " + name );
return;
}
System.out.print( "The " + name + " is: " );
ListNode current = firstNode;
while ( current != null ) {
System.out.print( current.data.toString() + " " );
current = current.next;
}
System.out.println( "\n" );
}
}
// EmptyListException Class
public class EmptyListException extends RuntimeException {
public EmptyListException( String name )
{
super( "The " + name + " is empty" );
}
}
// ListTest Class
import List;
import EmptyListException;
public class ListTest {
public static void main( String args[] )
{
List objList = new List(); // create the List container
// Create objects to store in the List
Boolean b = Boolean.TRUE;
Character c = new Character( '$' );
Integer i = new Integer( 34567 );
String s = "hello";
// Use the List insert methods
objList.insertAtFront( b );
objList.print();
objList.insertAtFront( c );
objList.print();
objList.insertAtBack( i );
objList.print();
objList.insertAtBack( s );
objList.print();
// Use the List remove methods
Object removedObj;
try {
removedObj = objList.removeFromFront();
System.out.println(
removedObj.toString() + " removed" );
objList.print();
removedObj = objList.removeFromFront();
System.out.println(
removedObj.toString() + " removed" );
objList.print();
removedObj = objList.removeFromBack();
System.out.println(
removedObj.toString() + " removed" );
objList.print();
removedObj = objList.removeFromBack();
System.out.println(
removedObj.toString() + " removed" );
objList.print();
}
catch ( EmptyListException e ) {
System.err.println( "\n" + e.toString() );
}
}
}
|
A stack is a constrained version of a link list, new nodes can be added to a stack and removed from the stack only at the top, a stack is sometimes referred to as a last-in first-out (LIFO) data structure.The two main methods used on a stack are push (add) and pop (remove).
*** stack picture ***
| Simple Stack example | // StackInheritance Class |
| Simple stack using composition | // StackComposition Class |
Another common data structure is the queue, this is like a line at a ticket stand, the first person in the line is serviced first and other customers join the line at the end. With queues nodes are removed only from the head of the queue and inserted only at the tail of the queue, this is referred to as first-in, first-out (FIFO) data structure. The insert and remove operations are sometimes referred to as enqueue and dequeue.
*** queue picture ***
| Queue example | // QueueInheritance Class
public class QueueInheritance extends List {
public QueueInheritance() { super( "queue" ); }
public void enqueue( Object o )
{ insertAtBack( o ); }
public Object dequeue()
throws EmptyListException { return removeFromFront(); }
public boolean isEmpty() { return super.isEmpty(); }
public void print() { super.print(); }
}
// QueueInheritanceTest Class |
Linked lists, stacks and queues are all linear data structures (sequences). A tree is a non-linear, two dimensional data structure with special properties. Tree nodes contain two or more links, a binary tree contains two links 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 first node in the left subtree and the right child is the first node in the right subtree. The children of a node are called siblings. A node with no children is acalled a leaf node.
*** tree picture ***
| Tree example | // TreeNode Class
class TreeNode {
// package access members
TreeNode left; // left node
int data; // data item
TreeNode right; // right node
// Constructor: initialize data to d and make this a leaf node
public TreeNode( int d )
{
data = d;
left = right = null; // this node has no children
}
// Insert a TreeNode into a Tree that contains nodes.
// Ignore duplicate values.
public synchronized void insert( int d )
{
if ( d < data ) {
if ( left == null )
left = new TreeNode( d );
else
left.insert( d );
}
else if ( d > data ) {
if ( right == null )
right = new TreeNode( d );
else
right.insert( d );
}
}
}
// Class Tree definition
public class Tree {
private TreeNode root;
// Construct an empty Tree of integers
public Tree() { root = null; }
// Insert a new node in the binary search tree.
// If the root node is null, create the root node here.
// Otherwise, call the insert method of class TreeNode.
public synchronized void insertNode( int d )
{
if ( root == null )
root = new TreeNode( d );
else
root.insert( d );
}
// Preorder Traversal
public synchronized void preorderTraversal()
{ preorderHelper( root ); }
// Recursive method to perform preorder traversal
private void preorderHelper( TreeNode node )
{
if ( node == null )
return;
System.out.print( node.data + " " );
preorderHelper( node.left );
preorderHelper( node.right );
}
// Inorder Traversal
public synchronized void inorderTraversal()
{ inorderHelper( root ); }
// Recursive method to perform inorder traversal
private void inorderHelper( TreeNode node )
{
if ( node == null )
return;
inorderHelper( node.left );
System.out.print( node.data + " " );
inorderHelper( node.right );
}
// Postorder Traversal
public synchronized void postorderTraversal()
{ postorderHelper( root ); }
// Recursive method to perform postorder traversal
private void postorderHelper( TreeNode node )
{
if ( node == null )
return;
postorderHelper( node.left );
postorderHelper( node.right );
System.out.print( node.data + " " );
}
}
// TreeTest Class
import Tree;
// Class TreeTest definition
public class TreeTest {
public static void main( String args[] )
{
Tree tree = new Tree();
int intVal;
System.out.println( "Inserting the following values: " );
for ( int i = 1; i <= 10; i++ ) {
intVal = ( int ) ( Math.random() * 100 );
System.out.print( intVal + " " );
tree.insertNode( intVal );
}
System.out.println ( "\n\nPreorder traversal" );
tree.preorderTraversal();
System.out.println ( "\n\nInorder traversal" );
tree.inorderTraversal();
System.out.println ( "\n\nPostorder traversal" );
tree.postorderTraversal();
System.out.println();
}
}
|