Advanced Data Structures in Java

University:
Kentucky State University
Course:
COS 129 | Introduction to JavaScripts
Academic year:

2021
Views:

120

Pages:

11
Author:

Joaquin Spears

Advanced Computer Science 3 Advanced Data Structures in Java Stacks ● Visualize a stack of books on a table. The first book you placed on the table will be at the very bottom and the last book you placed will be at the top. So when you take books from the stack, the first book you take out will be the last book you placed. In order to take a book from the middle of the stack, you must take out all the other books from the top until you reach the one you need, you can’t simply reach into the middle and take it out. This is known as the Last-In, First-Out(LIFO) principle. ● The stack class is a linear data structure, similar to an ArrayList, that uses this principle: Objects are removed in the reverse order from that in which they were inserted. ● Stack Operations ○ Stack stack = new Stack(); ■ Constructs a new stack with type String ○ String object = “hello”; stack.push(object); //or stack.push(“hello”); ■ Adds the object to the top of the stack and returns the object being “pushed” ○ object = stack.pop(); ■ Removes the object at the top of the stack and returns it ○ object = stack.peek(); ■ Returns the object at the top of the stack but does not remove it ○ stack.size(); ■ Returns number of elements in the stack ○ stack.isEmpty(); ■ Returns true if there is nothing in the stack ● However, Stacks are NOT meant for random access; They cannot be accessed using indexing; The following code shows you how to edit all the values in a stack. ○ You don't loop over a stack like this: for (int i = 0; i < stack.size(); i++) { //do something with ith item in stack } ○ Instead you pull items out of a stack until you're done, like this: Stack stack2 = new Stack(); while (!stack.isEmpty()) { //do something with top value of stack stack2.push(stack.pop()); //removes top value of stack and adds it to stack2; you can’t push the removed value back into the same stack because of Last-In First-Out } Queues ● Visualize a queue of people waiting in line at a checkout counter. Whoever arrives at the counter first is at the beginning of the line, and gets to check out their items and exit the store first. Those who arrived later will be at the end of the line, and they will be the last to check out their items and exit the store. This is known as the First-In First-Out(FIFO) principle. ● A queue interface is a linear data structure, similar to an ArrayList, that uses this principle: Objects are removed in the order in which they were inserted. ● Queue Operations: ○ Queue queue = new LinkedList(); ■ Constructs a new queue with type Integer ■ IMPORTANT: When constructing a queue object, you must use a new LinkedList object instead of a Queue object because Queue is an interface as opposed to a class ○ Integer object = 3; queue.offer(object); //or queue.add(3); ■ Adds the object to the end of the queue ○ object = queue.poll(); ■ Removes the object at the front of the queue and returns it ○ object = queue.peek(); ■ Returns the object at the front of the queue but does not remove it ○ queue.size(); ■ Returns number of elements in the queue ○ queue.isEmpty(); ■ Returns true if there is nothing in the queue ● As with stacks, you cannot loop through a queue like this: for (int i = 0; i < queue.size(); i++) { //do something with ith item in queue } ○ Instead you pull items out of a queue until you're done, like this: Queue queue = new LinkedList(); while (!queue.isEmpty()) { //do something with first value of queue queue.offer(queue.poll()); //removes first value of queue and adds it to the back; this works because of First-In First-Out } Mixing Stacks and Queues ● We often mix stacks and queues to achieve certain effects like reversing the order of the elements of a queue ○ Queue q = new LinkedList(); q.add(1); q.add(2); q.add(3); //[1, 2, 3] Stack s = new Stack(); while (!q.isEmpty()) { //Q -> S s.push(q.remove()); } while (!s.isEmpty()) { //S -> Q q.add(s.pop()); } System.out.println(q); //[3, 2, 1] LinkedList ● A sequence of nodes(objects) ● Each node has data(value) and a link(reference) to some other node ● The first node is known as a header and does not have data; the last node contains a null link(the link is not connected to anything) ● The node’s successor is the next node in a sequence ○ The last node has no successor ● The node’s predecessor is the previous node ○ The first node has no predecessor ● How to create a linked list(create the header and then create nodes linked to the header and to each other) ○ class LinkedList { Node head; // list head class Node { int data; Node next; Node(int d) { //constructor to create a new node data = d; } } } ○ LinkedList myList = new LinkedList<>(); Singly Linked List ● Successor only ● Longer run time for deletion and insertion ● Less space required ● List manipulations are faster Double Linked List ● ● ● ● Predecessor & Successor Easier deletion and insertion More space required List manipulations are slower because more links must be changed Binary Trees ● Tree: a non-linear data structure where data objects are organized in terms of hierarchical relationship ● Terminology: ○ Node: an object containing a data value and left/right children ■ Root: topmost node of a tree ■ Leaf: a node that has no children ■ Branch: any internal node; neither the root nor a leaf ■ Parent: a node that refers to this one ■ Child: a node that this node refers to ■ Sibling: a node with a common parent ■ Cousin: a node with a common grandparent ○ Subtree: the smaller tree of nodes on the left or right of the current node ○ Height: length of the longest path from the root to any node ○ Level/Depth: length of the path from a root to a given node ● Binary tree: a tree where each node can have a max of 2 children ● A basic tree node object stores data and refers to left and right ● IntTreeNode Class: ○ // An IntTreeNode object is one node in a binary tree of ints. class IntTreeNode { Int data; // data stored at this node IntTreeNode left; // reference to left subtree IntTreeNode right; // reference to right subtree // Constructs a leaf node with the given data. public IntTreeNode(int data) { this(data, null, null); } // Constructs a branch node with the given data and links. public IntTreeNode(int data, IntTreeNode left, IntTreeNode right) { this.data = data; this.left = left; this.right = right; } } ● Traversal: An examination of the elements in a tree ● As a tree is a non-linear data structure, there are multiple ways of traversing ○ Pre-order: process root node, then its left/right subtrees(N, L/R) ○ In-order: process left subtree, then root node, then right(L, N, R) ○ Post-order: process left/right subtrees, then root node(L/R, N) ● Binary Search Tree: A binary tree in which each non-empty node R that has the following properties ○ Elements of R’s left subtree contain values less than R’s data ○ Elements of R’s right subtree contain data more than R’s data ○ It’s left and right sub subtrees are also binary search trees Priority Queue: ● Stack: first in-last out(FILO) ● Queue: first in-first out(FIFO) ● Priority queue: least-first-out ○ “Smallest” element is the first one removed ○ If there are several “smallest” elements, the implementer decides which one to remove first(choose randomly, remove first smallest element added, etc.) ● Real-life example: Hospital emergency queue(patients with most critical situation get treated first ● Priority queue operations: ○ Queue pq = new PriorityQueue<>(); ■ Constructs a new priority queue with type String ○ Integer object = 3; pq.offer(object); ■ Inserts the specified element into this priority queue ○ object = pq.poll(); ■ Retrieves and removes the head of this queue (the "least" element), or null if this queue is empty. ○ object = pq.peek(); ■ Retrieves, but does not remove, the head of this queue, returning null if this queue is empty. ○ pq.size(); ■ Returns number of elements in this collection ○ pq.isEmpty(); ■ Returns true if there is nothing in the priority queue Hashing ● Hash set: a data structure in which keys (values) are mapped to array positions in a list by a hash function ● Hash Functions: functions which, when applied to the key, produce an integer which can be used as an address (index) in a hash table. The intent is that elements will be relatively randomly and uniformly distributed. ● Hash Table: uses a hash function to compute an index, also called a hash code/hash value, into an array of buckets or slots ● Code for a simple hash function ○ int hashFunction(int idNum) { return (idNum % TABLE_SIZE); } ● A perfect hash function will allow every single data input to have a different hash value(rare) within a suitable range ● When more than one element tries to occupy a single space in the hash table, it is known as a collision ● A good hash function minimizes the number of collisions; it may be any mathematical function that produces a relatively unique and random distribution of numbers ○ Set the size of the storages spaces to a prime number(helps generate a more uniform distribution of addresses) if hash function = value%tableSize ○ Hash function = sum of digits(for numbers) ○ Hash function = sum of ASCII code for each character in string % tableSize(for text) ● Handling Collisions: two main ways ○ Closed Hashing: computing a new hash location(index) inside array ■ Linear Probing: increment index by 1 until empty slot is found ■ Quadratic Probing: increment index by squares(1, 4, 9...) until empty slot is found ○ Open Hashing: Each slot in the array is a linked list, so the index is the one given by hash location but the object gets added to the linked list inside the array slot Type Advantages Open Hashing ● ● Disadvantages ● ● Closed Hashing Expanding the table and recreating a hash function is not needed Collision handling is much simpler ● All the elements (or pointers to the elements) are placed in contiguous storage. This will speed up the sequential searches when collisions do occur. As the list of collided elements (collision chains) becomes long, searching for a desired element begins to take longer and longer. Using pointers slows the algorithm: time required is to allocate storage for new nodes. ● As the number of collisions increases, the distance from the array index computed by the hash function and the actual location of the element increases, increasing search time. Clustering of elements The hash set has a fixed size. ● ●

Advanced Data Structures in Java

Related Documents

Recommended Documents

Description

Related Documents

Almost There!

Free up your schedule!

Take 5 seconds to unlock