The linked-allocation method of storage can result in both the efficient use of computer storage and computer time.
In Arrays, it has been mentioned that arrays are used to store a collection of similar items. The disadvantage of using arrays is that the maximum number of items to be stored in it has to be known at the time of writing the program. This number has to be specified in the array declaration. If the actual requirement is not known, the number has to be exaggerated to prevent run-time errors. This problem leads to wastage of precious memory as the memory allocated is more than required. Also, the process of insertion and deletion of elements in the array is tedious.
A list is an ordered set consisting of a variable number of elements to which insertions and deletions can be made. A list , which displays the relationship of adjacency between elements, is said to be linear.
If an uncertain number of elements have to be stored and frequent insertions and deletions are required, the data structure known as linked list can be used. Instead of storing the data items in contiguous memory locations, they are stored in the heap in scattered locations and links are used to connect an item to its neighbors. The concept of pointers is used to create these links.
Operations performed on lists include those , which are performed on arrays. However, they’re in one important difference in that the size of a list may be changed by updating. Indeed, updating may insert or delete elements, as well as change existing elements. The insertion and deletion of elements in a list is specified by position.
For example, we may want to delete the ith element of a list or insert a new element before or after the ith existing element.
Frequently, it may be required to insert or delete an element whose position in a list is based on the values of the other elements in the list (as in sorting). It may be required to insert or delete a given element to or from a list, respectively.
Other important operations besides insertion and deletion that are commonly performed on lists. Each element in a list is composed of one or more fields. A field can be considered to be the smallest piece of information that can be referenced in a programming language. A number of operations include the following:
- Combine two or more lists to form another list
- Split a list into a number of other lists
- Copy a list
- Determine the number of elements in a list
- Sort the elements of a list into ascending or descending order, depending on certain values of one or more fields within an element
- Search a list for an element, which contains a field having a certain value.