Data StructuresCOMS W1007Introduction to Computer ScienceChristopher Conway1 July 2003Linked ListsAn array is a list of elements with a fixed size, accessedby index. A more flexible data structure is the linked list.A linked list is composed of nodes, each of which containsa piece of data and a reference to the next node.0x640xfa null•A linked list can grow and shrink as much as needed.•Adding an element to a linked list is Θ(1).•Finding an element in a linked list is Θ(n).Doubly Linked ListsA doubly linked list allows us to traverse the listbackwards and forwards. Each node has a reference toboth the next and the previous node.null0x640xfa nullDouble linked lists allow us to very quickly (Θ(1)) removean element from either the front or the back of the list.Removing the last element of a singly linked list is Θ(n).QueuesA queue is a data structure in with two operations:•add puts an element at the end of the queue.•get takes an element from the front of the queue.We sometimes call a queue a FIFO: first-in, first-out.We can implement a queue with an array or a linked list.StacksA stack is a data structure with two operations:•push puts an element on top of the stack.•pop takes an element from the top of the stack.Stacks are also called LIFO queues: last-in, first-out.We can implement a stack with an array or a linked list.DictionariesA dictionary is an abstract data structure that stores adata element with a key and provides two operations:•add puts an element in the dictionary.•find takes a key and returns the correspondingelement.Keys and elements are comparable to words anddefinitions: you find a definition in the dictionary bysearching for the word (the key).Dictionaries and Linked ListsWe can implement a dictionary using a linked list.•add is easy. It’s an Θ(1) operations.•We can implement find by scanning the list. It’s anΘ(n) operation.We’ve seen algorithms that can search a list in Θ(lg n)operations. Can we make a better dictionary?Hash TablesA hash table is a collection of buckets. A hash functionmaps keys to buckets. Typically, the buckets are linkedlists and the buckets are held in an array; the data in thehashtable is an array of linked lists.01230x14 0xac...nullnull0x0f nullHash Table Operations: AddTo add an element to a hash table, we:•Run the hash function on the key. (Should be Θ(1))•Index the array and retrieve the correct bucket. (Θ(1))•Add the element to the bucket (linked list). (Θ(1))Adding an element to the hashtable is Θ(1).Hash Table Operations: FindTo find an element in a hash table, we:•Run the hash function on the key. (Should be Θ(1))•Index the array and retrieve the correct bucket. (Θ(1))•Find the element to the bucket (linked list). (?)If we choose the hash function and the number of bucketscarefully, we can make the average length of each bucketconstant with respect to the number of elements in thehash table.Finding an element in a properly implemented hash tableis Θ(1).Java CollectionsThe Java standard library provides implementations of allthese data structures, and many more besides.A trip through the java.util package documentationwill teach you a lot about interfaces, inheritance and thebehavior of data structures.All of the Java data structures work with elements andkeys of type Object. This means:•You should always cast the return value of a get tothe correct class.•You need to use the wrapper classes (Integer, etc.)to put primitive types into the data structures.java.util.HashtableJava’s implementation of a hash table is the classHashtable in java.util. Hashtable (and other“hashing” classes, like HashMap and HashSet) relies onthe hashCode method of Object:public int hashCode()Every class in Java inherits hashCode. We can overridehashCode, if necessary, but it’s best to leave hashing tothe experts. All of the built-in classes (String, Integer,etc.) have suitable hash functions.Generic ProgrammingConstantly casting the results of data structure getmethods is a pain. It’s also unnecessary: we almostalways want a collection of uniform type (or parent type, atleast). E.g., a linked list of String, or a hash tablemapping Integer keys (employee IDs) to Personnelobjects.Generic programming allows us to strongly typehigher-level data structures, using syntax similar tocreating an array:List<String> list = new LinkedList<String> ;The latest version of Java (1.5) allows you to do