Separate Chaining Resolution Using Linked List

A major disadvantage to open addressing is that each collision resolution increases the probability of future collisions. This disadvantage is eliminated in the second approach to collision resolution known as separate chaining using short linked lists. Separate chaining is an ordered collection of data in which each element contains the location of the next synonymous element. For example, in Figure 12, array element 001, Sarah Trapp, contains a pointer to the next element, Harry Eagle, which in turn contains a pointer to the third element, Chirs Walljasper. Linked list resolution uses a separate area to store collisions and chains all synonyms together in a linked list. It uses two storage areas, the prime area and the overflow area. Each element in the prime area contains an additional field, a link head pointer to a linked list of overflow data in the overflow area. When a collision occurs, one element is stored in the prime area and chained to its corresponding linked list in the overflow area. Although the overflow area can be any data structure, it is typically implemented as a linked list in dynamic memory. Figure 12 Shows the linked list from Figure 11 with three synonyms for address 001and three synonyms for address 007.

The linked list data can be stored in any order, but a last in-first out (LIFO) stack sequence and a key sequence are the most common. The LIFO sequence is the fastest for inserts because the linked list does not have to be scanned to insert the data. The element being inserted into overflow is simply placed at the beginning of the linked list and linked to the node in the prime area. Key sequenced lists, with the key in the prime area being the smallest, provide for faster search retrieval. Which sequence (LIFO or key-sequence) is used depends on the application.