This chapter deals with the importance of Linked list, type of Linked list and what a linked list is and after that we will come to know how it overcomes the limitations of array.
Introduction
List is a collection of similar type of elements. There are two ways of maintaining a list in memory. The first way is to store the elements of the list in a array, but array have some restrictions and disadvantages. The second way of maintaining a list in memory is through linked list.
If the memory is allocated before the execution of a program, it is fixed and cannot be changed. We have to adopt an alternative strategy to allocated memory only when it is required. There is a special data structure called linked list that provides a more flexible storage system and it does not require the use of arrays.
Linked lists
Linked list is a linear data structure. It is a collection of nodes of similar type. Basically, a node is a user defined structure. It is a collection of variables and pointers to store the data and address of the next node respectively. In the linked list, a node must have at least one pointer so that it can point to the next node.
Advantages
Linked lists have many advantages. Some of the very important advantages are-
- Linked lists are dynamic data structures.
- Efficient memory utilization.
- Insertion and deletion are easier and efficient.
- Many complex applications can be easily carried out with linked lists.
Key Terms
As we know, a linked list is a non-sequential collection of data items called nodes. Each node in a linked list has basically two fields.
1. Data field
2. Link field
The Data field contains an actual value to be stored and processed. And, the link field contains the address of the next data item in the linked list. The address used to access a particular node is known as a pointer.
Null Pointer: The link field of the last node contains NULL rather than a valid address. It is a null pointer and indicates the end of the list.
External Pointer: It is a pointer to the very first node in the linked list, it enables us to access the entire linked list.
Empty List: If the nodes are not present ina linked list, then it is called an empty linked list or simply empty list. It is also called the null list.
The value of the external pointer will be zero for an empty list. A linked list can be made an empty list by assigning a NULL value to the external pointer.
Start = NULL;
Types of Linked list
Basically, there are four type of linked list-
We will know about these all linked lists on next page
