Hash Tables

What are arrays?

• An array is a datastructure consisting of a collection of elements stored contiguously in memory.
• Arrays can be accessed directly or randomly i.e., arrays can be accessed using array index or subscript.
• Generally, arrays are consistent sets of a fixed number of a particular type of data items.

What are linked lists?

• A linked list is a datastructure consisting of a collection of elements stored randomly in memory.
• Linked List elements can only be sequentially accessed i.e., the traversing starting from the first node in the list by the pointer.
• Linked Lists are ordered sets comprising a variable number of any type of data items.

Time and Space Complexity

• Time complexity of an algorithm gives the measure of time taken by it to run as a function of the length of the input. Similarly, Space complexity of an algorithm quantifies the amount of space or memory taken by an algorithm to run as a function of the length of the input.
• Recall that suppose our input is an array of N elements, and our algorithm iterates through the array once, time complexity will be O(N). If we run two embedded loops to traverse the array N times, time complexity will be O(N2).