Data Structures Flashcards
A data structure used to store homogeneous elements at contiguous locations. Size must be provided before storing data.
Array
Search Time: O(n) for Sequential search, O(log n) for Binary Search (if sorted)
Array
Accessing Time: O(1), because elements are stored at contiguous locations
Array
Insertion Time: O(n), the worst case occurs when insertion happens at the beginning of the structure which then requires shifting all of the other elements
Array
Deletion Time: O(n), the worst case occurs when deletion happens at the beginning of the structure which then requires shifting all of the elements
Array
A data structure where each element is a separate object. Each element is comprised of two items – the data and a reference to the next node.
Linked list
In this type of linked list, every node stores the address / reference of next node. The last node’s reference is NULL.
For example 1->2->3->4->NULL
Singly linked list
In this type of Linked list, there are two references associated with each node. One that points to the next node and one that points to the previous node.
For example NULL23->NULL
Doubly Linked List
Advantage of this linked list data structure is that we can traverse in both directions and for deletion we don’t need to have explicit access to previous node.
Doubly Linked List
A linked list where all nodes are connected in either a singly linked list or doubly linked list.
Circular linked list
Advantage of this linked list data structure is that any node can be the starting node.
Circular linked list
Accessing time: O(n)
Search time: O(n)
Insertion of an Element : O(1), if we are at the position where we have to insert an element
Deletion of an Element : O(1), if we know the address of the node previous the node to be that is to be deleted.
Linked list
Eliminates unused memory when compared to an Array as nodes are only added when a new element is introduced.
Linked list
Insertions and deletions are easier when compared to an array because there is not need to shift elements.
Linked list
One big drawback of this data structure is that random access is not allowed. Unlike arrays, where we can access the n’th element in O(1) time. In this data structure, it would take O(n) time.
Linked list
An abstract data type that serves as a collection of elements, with two principal operations: push, which adds an element to the collection, and pop, which removes the last element that was added. Both operations take place at the top end of the structure and it can be implemented by using both an array or a linked list.
Stack
Insertion : O(1)
Deletion : O(1)
Access Time : O(n), worst case
Insertion and Deletion are only allowed on one end.
Stack or LIFO
A data structure used for maintaining function calls (the last called function must finish execution first). We can always remove recursion with the help of a __________. They are also used in cases where we have to reverse a word or to implement back functionality in web browsers.
Stack
An abstract data structure that serves as a collection of elements, with two principal operations: enqueue, the process of adding an element to the end of collection, and dequeue, the process of removing the first element in the collection. It can be implemented by using an array or a linked list.
Queue or FIFO
A data structure that best handles any situation where resources are shared among multiple users and served on first come first server basis. Examples include CPU scheduling, Disk Scheduling.
Queue
Arrays, Linked Lists, Stack and queues
Linear data structures
Hierarchical data structures
Trees
A data structure in which each node has at most two children, which are referred to as the left child and the right child. It is implemented mainly using Links.
Binary Tree
A _______ is represented by a pointer to the topmost node. If the _______ is empty, then the value of root is NULL.
A _______ node contains the following parts:
- Data
- Pointer to left child
- Pointer to right child
Binary Tree
