Linked List

linked list is a dynamic and linear data structure.

The Concept Of Link List

  1. Link list used for the dynamic memory allocation.
  2. Array and link list both are the linear data structure.
  3. When we want to represent several lists by using arrays of varying size, either we have to represent.
  4. each list using a separate array of maximum size or we have to represent each of the lists using one single array.
  5. The first one will lead to wastage of storage, and the second will involve a lot of data movement.
  6. A linked list is a list of elements in which the elements of the list can be placed anywhere in memory, and these elements are linked with each other using an explicit link field, that is, by storing the address of the next element in the link field of the previous element.

Structure of node

struct node
	int data;
 	struct node *next;

Representation of link list

Link list consists a series of structure. Each structure consists of a data field and address field. Data field consists data part and the address field contains the address of the successors.

Advantage of Link list

  1. Link list is an example of dynamic data structure. They can grow and shrink during the execution of program.
  2. Efficient memory utilization. Memory is not pre allocated like static data structure. The allocation of memory depends upon the user ,i.e no need to pre-allocate memory
  3. Insertion and deletion easily performed.
  4. Linear Data Structures such as Stack,Queue can be easily implemeted using Linked list
  5. Faster Access time,can be expanded in constant time without memory overhead

Points to Remember

  1. Linked lists are used when the quantity of data is not known prior to execution.
  2. In linked lists, data is stored in the form of nodes and at runtime, memory is allocated for creating nodes.
  3. Due to overhead in memory allocation and deallocation, the speed of the program is lower.
  4. The data is accessed using the starting pointer of the list.