Data Structures and Algorithms

Data structure is a programmatic way of collecting, storing and organizing data. Anything that can store data can be called as a data structure, hence Integer, Float, Boolean, Char etc, all are data structures. They are known as Primitive Data Structures.

In this repository, the following are the Abstract types of data structures:

1. Linked List
2. Doubly Linked List
3. Queue
4. Stack
5. Hash Table
6. Tree

Basic Operations:

The data in the data structures are processed by certain operations that needs to be performed, such as:

• Traversing;
• Searching;
• Insertion;
• Deletion;
• Sorting.

LINKED LIST

Linked List is a sequence of links which contains items. Each link contains a connection to another link. The important terms to understand the concept of Linked List are:

• Link − Each link of a linked list can store a data called an element.
• Next − Each link of a linked list contains a link to the next link called Next.

Types of Linked List

1. Simple Linked List − Item navigation is forward only.
2. Doubly Linked List − Items can be navigated forward and backward.

Basic Operations:

1. Insertion − Adds an element at the beginning of the list.
2. Deletion − Deletes an element at the beginning of the list.
3. Display − Displays the complete list.
4. Search − Searches for an element using the given key.
5. Delete − Deletes an element using the given key.
6. Reverse - Moves the head list to the last node.

SINGLY LINKED LIST

Linear Linked list is the default linked list and a linear data structure in which data is not stored in contiguous memory locations but each data node is connected to the next data node via a pointer, hence forming a chain.

• The element in such a linked list can be inserted in 2 ways:
  • Insertion at beginning of the list.
  • Insertion at the end of the list.

• Time Complexities:

traverse	Search	Insert	Delete
O(n)	O(n)	O(1)	O (n)

• Space Complexities: O(n)

DOUBLY LINKED LIST

Doubly Linked List is a variation of Linked list whereby navigation is possible in both ways, either forward and backward easily as compared to Single Linked List. The important terms to understand the concept of doubly linked list which linked lists don't have are:

1. Prev − Each link of a linked list contains a link to the previous link called Prev.
2. LinkedList − A Linked List contains the connection link to the first link called First and to the last link called Last.

• Other Basic Operations:

1. Insert Last − Adds an element at the end of the list.
2. Delete Last − Deletes an element from the end of the list.
3. Display forward − Displays the complete list in a forward manner.
4. Display backward − Displays the complete list in a backward manner.

• Time Complexities:

traverse	Search	Insert	Delete
O(n)	O(n)	O(1)	O (n)

• Space Complexities: O(n)

• NODE: A Node in a linked list holds the data value and the pointer which points to the location of the next node in the linked list. In other words, it is a data value and a pointer (pointing to the next node) put together.

QUEUE

Queue is an abstract data structure, somewhat similar to Stacks. Unlike stacks, a queue is open at both its ends. One end is always used to insert data (enqueue) and the other is used to remove data (dequeue). Queue follows First-In-First-Out methodology, i.e., the data item stored first will be accessed first.

Basic Operations:

1. enqueue() − add (store) an item to the queue.
2. dequeue() − remove (access) an item from the queue.
3. peek() − Gets the element at the front of the queue without removing it.
4. isfull() − Checks if the queue is full.
5. isempty() − Checks if the queue is empty.

• Time Complexities:

traverse	Search	Enqueue	Dequeue
O(n)	O(n)	O(1)	O (1)

• Space Complexities: O(n)

STACK

Stack is an abstract data type with a bounded(predefined) capacity. It is a simple data structure that allows adding and removing elements in a particular order.

• Basic Operations:

1. Stack is an ordered list of similar data type.
2. Stack is a LIFO(Last in First out) structure or we can say FILO(First in Last out).
3. push() function is used to insert new elements into the Stack and pop() function is used to remove an element from the stack. Both insertion and removal are allowed at only one end of Stack called Top.
4. Stack is said to be in Overflow state when it is completely full and is said to be in Underflow state if it is completely empty.

• Time Complexities:

traverse	Search	push	pop
O(n)	O(n)	O(1)	O (1)

• Space Complexities: O(n)

HASH TABLE

A hash table (hash map) is a data structure which implements an associative array abstract data type, a structure that can map keys to values. A hash table uses a hash function to compute an index into an array of buckets or slots, from which the desired value can be found.

Ideally, the hash function will assign each key to a unique bucket, but most hash table designs employ an imperfect hash function, which might cause hash collisions where the hash function generates the same index for more than one key. Such collisions must be accommodated in some way.

• Hash Algorithm:

1. input the string argument n
2. find the ascii value of each character in n
3. add the ascii values as value
4. return the remainder of value divided by 1000

• Hash function:

Start
input "Raymond"
R = 82, a = 97, y = 121, m = 109, o = 111, n = 110, d = 100
82 + 97 + 121 + 109 + 111 + 110 + 100 = 730
return 730 % 1000 = 730
End

• In code:

def awesome_hash_func(value=None):
    # do awesome stuff here
    return awesome_hash_value

hash_value = awesome_hash_func("raymond")
print(hash_value) # prints 730

Basic Operations:

1. get - Searches for the key using a given element or value.
2. set- Adds an element to the table using the key;
3. delete - Deletes an element or value and its key using the given element;
4. has - Searches if the key is in the table using the given key;
5. hash - Creates the hash key;
6. get_keys - Displays the elements or values in the table.

• Time Complexities:

traverse	Search	Insert	Delete
N/A	O(1)	O(1)	O (1)

• Space Complexities: O(n)

An Important point to note is Hash Collision.

Hash Collision:

This occurs when a hash function maps two different keys to the same table address, a collision is said to occur. This is solved by giving the second element a different key to a different table address; involves re-hashing either by

• linear probing: A simple re-hashing scheme in which the next slot in the table is checked on a collision. OR
• quadratic probing: A re-hashing scheme in which a higher (usually 2nd) order function of the hash index is used to calculate the address.

TREE

A tree is a widely used abstract data type (ADT) that simulates a hierarchical tree structure, with a root value and subtrees of children with a parent node, represented as a set of linked nodes. It is used mostly for representing hierarchical information.

A tree data structure can be defined recursively (locally) as a collection of nodes (starting at a root node), where each node is a data structure consisting of a value, together with a list of references to nodes (the "children"), with the constraints that no reference is duplicated, and none points to the root.

Terminologies:

• Root Node - The topmost node in a tree and will not have a parent.
• Nodes - A node is a structure which may contain a value or condition, or represent a separate data structure
• Leaf Nodes - Any node that does not have child nodes.
• Parents - A node that has a child is called the child's parent node. A node has at most one parent, but possibly many ancestor nodes, such as the parent's parent.
• Children
• Ancestor - A node reachable by repeated proceeding from child to parent.
• Levels

• Time Complexities:

traverse	Search	Insert	Delete
O(log(n))	O(log(n))	O(log(n))	O(log(n))

• Space Complexities: O(n)

ACKNOWLEDGEMENT

Once again I thank @jirevwe and @yudori for helping me, ensuring it's python-like and most importantly the encouragement. Lastly, I thank the 8 people that saw this repo and gave it a star, I'm still blushing. Thank you....

For more details on data structures and more on what I did and didn't do check this repo @ebosetalee - Understanding Python