Linked List is a linear collection of the data elements. It is data structure consisting of collection of nodes which together represents the sequence. Each node consists of:
o Data
o Reference (Address to next node)
• Structure of Linked List allows the efficient insertion or removal of an element at any position
• Access time is linear in Linked List
• Random access is not feasible in Linked List
• Arrays have better cache locality compared to Linked List
Cache Locality(Locality of Reference or Principal of Locality)
Tendency of a processor to access same set of memory location repetitively over a shorter period of a time.
The list items could be easily removed or re-inserted without any reallocation or reorganization of an entire structure because data items could not be restored contiguously. In the disk, while restructuring in an array is a long process. Linked List are dynamic, so the length of the list can be increased or decreased depending upon situation. However, the length of the array remains same as that at the time of deceleration and cannot be changed. It is costly to insert and delete elements in an array.
In Linked List Memory allocation is done during the run time. There by, Linked List uses dynamic memory allocation.
- Process queue in operating system, actually doubly linked list of process in ready state. There by, it process at the front of linked list denotes the one to be operated next
- Where insertion and deletion is greater than retrievels
Insertion in the Linked List, is a proccess of adding elements in the Linked List. Insertion in the Linked List is of three types:
-
Insert at Head
-
Insert at Tail
-
Insert in Middle
Deletion in the Linked List, is a process of removing the elements from the Linked List. Deletion is of three types:
-
Deletion at the Head
-
Deletion at the Tail
-
Deletion in the Middle
Searching , is a process of Searching elements in the Linked List. Search could be done by:
-
Iteration
-
Recursion
Reversing, is a process of changing the order of elements in the linked list. Reversing is done by:
-
Iteration
-
Recursion
Operator overloading, is a process of overloading in order to perform specific operation in the list.
A special customized loop is setup, to print up the elements in the linked list and print the value in it till NULL is reached.
The reason behind this is:
-
The complexity of the Merge sort remain as that of O(nlogn) despite the fact that, we find the mid-point in the Linked List
-
In Linked List, we can insert a node in between in O(1) time and space complexity ; if we are given reference to the previous node
-
We do not have random access to elements in the Linked List
-
Linked List follows sequential pattern, while reffering to any node. So, that could be a overhead for quick sort. Merge sort access the data sequentially.
When the tail node points to the head node instead of pointing to the NULL Pointer; then that linked list is called as Circular Linked List.
Some of the Applications of the Circular Linked List are:
-
In many C.P.U Algorithm, you need Circular Linked List to perform a given operation multiple times
-
In the implementation of forming different types of Queue
-
In the implementation of the advanced algorithm such as Fibonacci Heap
List is included in the given C++ Program. The function is there to add all its utility and is managed
This function is used to add the elements at the end of the list
This function is used to sort the given list
This function is used to add the element at the front of the list
As, the name goes; This function removes the last element from the list
This function removes the first element from the list
This function is used to insert the element in the linked list
This function is used to remove the element in the given list
This function removes the given element from the list
This function is used to print the first element in the list
Stack is a data structure, which represents the collection of the objects. A item could be added and stored in a stack using push operation. An object can be retrieved using pop operation, to remove an item from the stack. A item could be inserted at the top of the stack. A item could be either removed either from top or bottom of the stack. Their are two types of stack:
- LIFO(Last In First Out)
- FIFO(First In First Out)
Stack could be explained with the help of real life examples:
- Stack of books
- ATM Machine
- Pile of Plates
Vectors are resizable arrays
In a stack, we can follow operations such as push(), pop(), remove(), empty().
FIFO stack is basically a type of Queue.
Stacks have several applications in the Computer Programming. LIFO is used to retrieve, recently used objects from cache. FIFO stacks is used to ensure the data is retrieved in the order it was entered. Stacks are basically created at the background, while application was running in front. If stack, runs out of memory such situation is termed as Stack Overflow .
A stack could be generalized using templated class template . You can generalize the given code in a following way as told in file generalization of stack
Queue is a data structure designed to operate in FIFO (First in First out) context. In queue elements are inserted from rear end and get removed from front end operations called 'enqueued' and 'dequed' respectively. Queue class is container adapter. Container is an objects that hold data of same type. Queue can be created from different sequence containers.- Circular Array based
- Linked List based
Out of the two Circular Array based implementation is quite lengthier than the Linked List based implementation.
Note: In a circular array (n-1) position is adjacent to the first element of the circular array.
Applications: Queue is used for maintaining the whatsapp status messages, placing the delivery order on e-commerce sites like flipkart, amazon or myntra.
- q.push() : Adds element in the list
- q.front() : Returns the first element
- q.pop() : Removes the element
- q.empty() : Check wheather the queue is empty or not
- In Deque, insertion and deletion could be done from both the ends.
- Deque are the sequence containers with dynamic size, that can be expanded or contracted at both the ends
- Some functionalities are much more in deque. As, we can extend the vector only in one direction
- Deque can extend in both the direction like linked list
- Deque does not contain an internal storage. Deque are more complex than vector internally
- In certain operations where insertion or deletion is done at a positon other than begining or end. In such situation, Deque perform the worst.
Binary Trees are build using recursion. It is a top-down appraoch.
Algorithm
- Build a root
- Recursively build left and right subtree
More info about Binary Tree
Binary Operation such as Insertion, Deletion, Search, Ordering decide which Data Structure is helpful for a particular problem. As the name goes, in Binary Trees atleast one node should be connected to atleast 2 nodes. The nodes in the Binary Trees is connected using the adress. The basic node is called as the root node. And , the subsequents of root node are called as children node. Moreover, the nodes which do not have any children are called as Leaf Nodes.
The different types of Traversal in a Binary Tree are:
- In-Order Traversal ( ROOT - > LEFT - > RIGHT )
- Pre-Order Traversal ( LEFT - > ROOT - > RIGHT )
- Post-Order Traversal ( LEFT - > RIGHT - > ROOT )
- Level-Order Traversal ( Recursive Approach )
/desktop <-- root
/ \
...
my computer
/ \
local (c): local (d):
/ / | \
... prg1 prg2 prg3
A skew tree is one where each root node has one child node or no node. In case of a Skew Tree, it takes O(n) time to calculate the value or the hieght of the given tree.
Some common problems in the Binary Tree:
- Counting Number of Nodes in the Binary Tree
- Finding the longest chord in the Binary Tree
- Binary Tree Sum Replacement
- Height Balanced Binary Tree
- Nodes at Distance K from Given Node
- Lowest Common Ancestor
- Maximum Sum Path from Any Node to Node
- Shortest Distance between the Nodes of the Binary Tree
Priority Queue STL is used to work efficiently when we need to code to find the output based on some term and condition. For eg, When you go to bank and they say that they would do the work first for the persons who are more than 70 years of age and there are 1000 people standing in queue. So, that is a way they could easily priortize and add the people.
Hash Map is their to do support insertion, deletion, and search in average case-constant time O(1) time complexity. This data is not useful if you want to do some kind of an order of an element.
Hash ["string key"] ==> Integer Value
Array is the simplest kind of hashing because, in an array we maintain index and a value. Hash Table is an array of a fixed size.
Operations in Hash Table
Insert - T[h(key)] = value Delete - T[h(key)] = NULL Search - return T[h(key)]
If h("John") = h("Joe") then collision cannot be avoided. Collision cannot be avoided only its chances can be reduced by using a good hash function.
A "good hash function" has following properties:
- Reduce a chance of collision - Distribute Key Uniformly over the Table
- Should be fast to compute
How Hash Table is build
h(key) = key % tablesize