Linked List

What is Linked List?

* A list implemented by each item having a link to the next item.

* It is a series of nodes. 

* Each node consists of 2 parts viz. 

        1. Data part

        2. Pointer part.

* Pointer part stores the address of next node.

Node:

1. Head points to the first node. 

2. Last node points to NULL. 

Basic Concepts:

The four basic list operations are insertion, deletion, retrieval, and traversal.

Insertion is used to add a new element to the list. 

Deletion is used to remove an element from the list. 

Retrieval is used to get the information related to an element without changing the structure of the list. 

Traversal is used to traverse the list while applying a process to each element.

Insertion:

List insertion can be ordered or random.

Ordered lists:

They are maintained in sequence according to the data or, when available, a key that identifies the data. 

Key:

A key is one or more fields within a structure that identifies the data.

Example:

They keys are Social Security number and the universal product code on retail merchandise.

Random lists or Unordered lists or chronological lists:

1. In random lists there is no sequential relationship between two elements.

2. Although there are no restrictions on inserting data into a random list, computer algorithms generally  insert data at the end of the list.

Important:

1. Data must be inserted into ordered lists so that the ordering of the list is maintained.

2. To determine where the data are to be placed, computer scientists use a search algorithm.

Deletion:

1. Deletion from a general list requires that the list be searched to locate the data being deleted. 

2. Any sequential search algorithm can be used to locate the data.

3. Once located, the data are removed from the list.

4. When data are deleted from a random array, the data following the deleted item must be shifted to replace the empty element.

Retrieval:

1. List retrieval requires that data be located in a list and presented to the calling module without changing the contents of the list.

2. As with both insertion and deletion, a search algorithm can be used to locate the data to be retrieved from a list.

Traversal:

1. List traversal processes each element in a list in sequence. 

2. It requires a looping algorithm rather than a search.

3. Other processes can be used with a linear list, such as sorting the list or totaling the value of all elements in the list