Linked List Implementation
This tutorial for is only to gain your knowledge exam will not ask any coding question in CCAT. If you don’t want to learn you can skip this .
I will highly recommend please don’t skip this will help you a lot in future.
Lets Do some exercises :
1. What is the time complexity to count the number of elements in the linked list?
a) O(1)
b) O(logn)
c) O(n)
d) O(n2)
Ans : c
To count the number of elements, you have to traverse through
the entire list, hence complexity is O(n).
2. What is the space complexity for deleting a linked list?
a) O(1)
b) O(n)
c) Either O(1) or O(n)
d) O(logn)
a
You need a temp variable to keep track of current node,
hence the space complexity is O(1).
3. Which of these is not an application of linked list?
a) To implement file systems
b) For separate chaining in hash-tables
c) To implement non-binary trees
d) Random Access of elements
Answer: c
Explanation: When temp is equal to data, the position of data is returned.
4. What kind of linked list is best to answer question like “What is the item at position n?”
a) Singly linked list
b) Doubly linked list
c) Circular linked list
d) Array implementation of linked list
Ans : d
5. Linked lists are not suitable to for the implementation of?
a) Insertion sort
b) Radix sort
c) Polynomial manipulation
d) Binary search
Ans : d
Because it cant be implemented using linked list
Tree In Data Structure
Very important topic in exam so read carefully.
A tree whose elements have at most 2 children is called a binary tree. Since each element in a binary tree can have only 2 children, we typically name them the left and right child.
Basic Operations Performed :
Insert − Inserts an element in a tree/create a tree.
Search − Searches an element in a tree.
Preorder Traversal − Traverses a tree in a pre-order manner.
Inorder Traversal − Traverses a tree in an in-order manner.
Postorder Traversal − Traverses a tree in a post-order manner.
What is Searching? :
Searching is the process of finding a given value position in a list of values.
It decides whether a search key is present in the data or not.
It is the algorithmic process of finding a particular item in a collection of items.
It can be done on internal data structure or on external data structure.
Types Of Searching :
1. Sequential Search
2. Binary Search
1. Sequential Search
Sequential search is also called as Linear Search.
Sequential search starts at the beginning of the list and checks every element of the list.
It is a basic and simple search algorithm.
Sequential search compares the element with all the other elements given in the list. If the element is matched, it returns the value index, else it returns -1.
Sequential search is applied on the unsorted or unordered list when there are fewer elements in a list.
2. Binary Search :
Binary Search is used for searching an element in a sorted array.
It is a fast search algorithm with run-time complexity of O(log n).
Binary search works on the principle of divide and conquer.
This searching technique looks for a particular element by comparing the middle most element of the collection.
It is useful when there are large number of elements in an array.
Binary searching starts with middle element. If the element is equal to the element that we are searching then return true. If the element is less than then move to the right of the list or if the element is greater than then move to the left of the list. Repeat this, till you find an element.
Difference Between Linear and Binary Search :
A linear search scans one item at a time, without jumping to any item. In contrast, binary search cuts down your search to half as soon as you find the middle of a sorted list.
In linear search, the worst case complexity is O(n), where binary search making O(log n) comparisons.
Time taken to search elements keep increasing as the number of elements is increased when searching through linear process. But binary search compresses the searching period by dividing the whole array into two half.
Linear search does the sequential access whereas Binary search access data randomly.
Input data needs to be sorted in Binary Search and not in Linear Search.
In linear search, performance is done by equality comparisons. In binary search, performance is done by ordering comparisons.
Binary search is better and quite faster than linear search.
Linear search uses sequential approach. But, binary search implements divide and conquer approach.
Linear search is quick and easy to use, but there is no need for any ordered elements. Where binary search algorithm is tricky, and elements are necessarily arranged in order.
The best case time in linear search is for the first element that is O(1). And the other side O(1) is the middle element in binary search.
Linear search can be implemented in an array as well as in linked list, but binary search can’t be implemented directly on linked list.
Binary search is efficient for the larger array. If the amount of data is small, then linear search is preferable because this searching process is fast when data is small.
Time and Space complexity :
| Sorting Algorithm | Time Complexity | Space Complexity | ||
|---|---|---|---|---|
| Best Case | Average Case | Worst Case | Worst Case | |
| Bubble Sort | Ω(N) | Θ(N2) | O(N2) | O(1) |
| Selection Sort | Ω(N2) | Θ(N2) | O(N2) | O(1) |
| Insertion Sort | Ω(N) | Θ(N2) | O(N2) | O(1) |
| Merge Sort | Ω(N log N) | Θ(N log N) | O(N log N) | O(N) |
| Heap Sort | Ω(N log N) | Θ(N log N) | O(N log N) | O(1) |
| Quick Sort | Ω(N log N) | Θ(N log N) | O(N2) | O(N log N) |
| Radix Sort | Ω(N k) | Θ(N k) | O(N k) | O(N + k) |
| Count Sort | Ω(N + k) | Θ(N + k) | O(N + k) | O(k) |
| Bucket Sort | Ω(N + k) | Θ(N + k) | O(N2) | O(N) |
Note : In whatever condition dont forget above chart read 100 time because 2,3 fix question on above chart in exam .
Sorting :
Sorting is a process of ordering or placing a list of elements from a collection in some kind of order. It is nothing but storage of data in sorted order. Sorting can be done in ascending and descending order. It arranges the data in a sequence which makes searching easier.
Types of Sorting :
1. Bubble Sort
2. Insertion Sort
3. Selection Sort
4. Quick Sort
5. Heap Sort
1. Bubble Sort :
Bubble Sort is the simplest sorting algorithm that works by repeatedly swapping the adjacent elements if they are in wrong order.
Keep in mind following points :
Worst and Average Case Time Complexity: O(n*n). Worst case occurs when array is reverse sorted.
Best Case Time Complexity: O(n). Best case occurs when array is already sorted.
Auxiliary Space: O(1)
Boundary Cases: Bubble sort takes minimum time (Order of n) when elements are already sorted.
Sorting In Place: Yes
Stable: Yes
2. Insertion Sort :
Insertion sort is a simple sorting algorithm that works the way we sort playing cards in our hands.
Time Complexity: O(n*2)
Auxiliary Space: O(1)
Boundary Cases: Insertion sort takes maximum time to sort if elements are sorted in reverse order. And it takes minimum time (Order of n) when elements are already sorted.
Algorithmic Paradigm: Incremental Approach
Sorting In Place: Yes
Stable: Yes
Insertion sort is used when number of elements is small. It can also be useful when input array is almost sorted, only few elements are misplaced in complete big array.
3. Selection Sort :
he selection sort algorithm sorts an array by repeatedly finding the minimum element (considering ascending order) from unsorted part and putting it at the beginning.
Time Complexity: O(n2) as there are two nested loops.
Auxiliary Space: O(1)
The good thing about selection sort is it never makes more than O(n) swaps and can be useful when memory write is a costly operation.
4. Quick Sort :
Like Merge Sort, QuickSort is a Divide and Conquer algorithm. It picks an element as pivot and partitions the given array around the picked pivot. There are many different versions of quickSort that pick pivot in different ways.
Always pick first element as pivot.
Always pick last element as pivot (implemented below)
Pick a random element as pivot.
Pick median as pivot.
5. Heap Sort :
Heap sort is a comparison based sorting technique based on Binary Heap data structure. It is similar to selection sort where we first find the maximum element and place the maximum element at the end. We repeat the same process for remaining element.
Heap sort is an in-place algorithm.
Time Complexity: Time complexity of heapify is O(Logn). Time complexity of createAndBuildHeap() is O(n) and overall time complexity of Heap Sort is O(nLogn).
Note : This tree material is very very important almost 5,6 questions 100 % will come from all these topics . so don’t miss anything .
we will cover lots of objective question in our question program so keep practice .
prefix Postfix infix on this topic fix 2,3 mathematical problems will come .
On time complexity chart fix 2,3 questions .
1,2 questions on tree .