Array vs. Linked List vs. Hash Table

Array

An array is a linear data structure consisting of a collection of similar data type elements, each identified by at least one index or key. The size of the array must be specified at the time of its declaration. It is fixed and cannot be resized during runtime. In the array, elements are organized sequentially, one after another within a single block of memory.

• Access – It supports efficient random access, which means that its elements can be accessed directly using their index.
• Insertion – If the insertion site is located at the beginning or in the middle of the array, all the elements located on the right are moved one index forward. If the array is full, a new larger array is created. Inserting is very efficient at the end of the array.
• Deletion – If the deleted element is located at the beginning or in the middle of the array, all the elements located on the left are moved one index backwards to avoid leaving an empty space in memory. This guarantees that the elements are stored in contiguous space in memory. Removal is very efficient at the end of the array because only the last element is deleted.
• Search – The array must be sequentially checked until a match is found.

Linked List

A linked list is a linear data structure consisting of nodes (elements) where each node contains a data field and a reference (link) to the next node in the list. Extra memory space for a pointer is required with each element of the list. The first node is called the head. The last node is called the tail. The size of the linked list doesn’t need to be specified at the time of its declaration. It allows dynamic resizing at runtime. There is no requirement for the list’s elements to be stored contiguously in memory because pointers are used to link the data.

• Access – Random access is not allowed. Elements must be accessed sequentially starting from the first node.
• Insertion – It could be implemented efficiently if the element is inserted at the head (first node) because there is no relinking of nodes to be performed since the first node has no preceding node. Inserting a node at the middle requires the preceding node to refer to the node we want to add. Inserting a node at the end (tail) requires the preceding node to refer to the new end of the list.
• Deletion – It could be implemented efficiently if the element is removed from the head (first node) because there is no relinking of nodes to be performed since the first node has no preceding node. Removing a node from the middle requires preceding node to refer to the node before the one we want to remove. Removing a node from the end (tail) requires the preceding node to become the new end of the list (i.e., points to nothing after it).
• Search – The linked list must be sequentially checked until a match is found.

Hash Table

A hash table is an unordered collection of elements consisting of key-value pairs. A hash table is implemented using a hashing function. It improves data access times. Rather than sorting the data according to a key, it computes the location of the data from the key. In simple terms, it computes an index value from the key of the desired record. At that index value, the record is stored/retrieved.

A good hash function is essential for hash table performance. A poor choice of hash function is likely to lead to an excess amount of collisions which will degrade performance significantly. Also some hash functions are computationally expensive and the amount of time (and, in some cases, memory) taken to compute the hash may be burdensome. The primary requirements in implementing a good hash function for a given data type are that it should be deterministic (equal keys must produce the same hash value), efficient to compute and to distribute the keys uniformly.

The complexity of a hash table depends on the hash function picked. The more collisions it generates, the more the complexity tends toward Θ(n). Hash tables have a Θ(1) complexity in best and average case scenarios but fall to Θ(n) in their worst-case scenario.

Conclusion

Arrays and linked lists are data structures which store a collection of elements in a specific order. In arrays, the order of elements is fixed and they’re accessed sequentially by index number. In linked lists, the nodes can be in any place in memory, because each of them has a pointer to the next node. A hash table is different from either because it doesn’t store its elements in any particular order. It is an unordered collection of elements with different (usually quick) access times, which in practice can be somewhere between the array and the linked list based on how exactly it is implemented and used.

In short, if you have data that doesn’t use too many inserts or deletes, and access the items frequently out of order, use an array. If you need data that can be quickly inserted and deleted into and is accessed mostly in sequential order, use a linked list. If you need a fast traversal then a hash table with a good hash function will be a better choice.