Data-Structures

List

1. ArrayList
2. LinkedList

(1) ArrayList

Key points:

• Resizable
• Allow retrieving elements by their index
• Orderd collection
• Allows Duplicate and null values

Trade Off:

• Dose not support inserting data in the middle of the list
• Dose not support primitive types

Details and Methods

(2) LinkedList

Key points:

• Almost like ArrayList
• Internally way of storing data is different
• It store an object called "nodes" which connect each other and form a chain
• Allow inserting data in the middle of the list

Trade Off:

• Uses more overall memory than a ArrayList
• Slower when looking up a value in a random index

Details and Methods

List Example: ArrayList vs LinkedList

Time Complexity ArrayList Vs LinkedList:

ADTs: (Abstruct Data Type)

The idea of different way of implementing same operation is called ADT.

1. Stack
2. Queue

(1) Stack

Key points:

• Last In First Out (LIFO)
• push : Add an element to the TOP
• pop : Remove the TOP element
• peek : Examine the TOP element (Dose not remove it)

Trade Off:

• Dose not allow to see how many elements in a stack

Details and Methods

(2) Queue

Key points:

• First In First Out (FIFO)
• add : Add an element to the BACK of the queue(AKA: enqueue)
• remove : Remove an element from the FRONT of the queue (AKA: dequeue)
• peek : Examine the FRONT element (Dose not remove it)

Trade Off:

• Dose not allow to see how many elements in a queue

Details and Methods

ADT Example: Stack vs Queue

Set

A Collection of unique values. We dont think of a set as having any indexes. We just add things to the set in general.

Key points:

• No duplicate value allowed
• Perform Add, Remove, Search(Contain) operations

Details and Methods

Set Example: Set

Time Complexity HashSet:

Map

A Collection that stores pairs, where each pair consists of first half called "Key" and second half called "Value"

Key points:

• Sometimes called "dictionary/ associative array/ hash"
• Basic operations put, get, remove

Details and Methods

Map Example: Map

Performance Analysis (List vs Set vs Map)

Reading a Long Text file word by word List took pretty long time than Set or Map, wheather Set and Map took almost same time. Note: every word is unique word. The program tested on Intel Core i3 processor with 3.30 GHz in 12 Gigs of Ram.

Screen Shot 1:

Screen Shot 2:

Screen Shot 3:

Above Program Link - (CountWords)

Application Using These Data Structures - (WordLader-Ngrams)

DQueue

Acknowledgement

Stanford(CS-106B) : http://stanford.edu/class/archive/cs/cs106b/cs106b.1184/index.shtml

Authors

Apurba Biswas