Introduction To Linked lists

 LINKED LIST

INTRODUCTION:

The Linked List is a popular linear data structure in which the members are not stored in contiguous memory regions.

A linked list is an ever-changing data structure.

A linked list is a collection of data structures that are linked together.

Ø STRUCTURE OF LINK LIST :

Each link in the linked list is referred to as a "Node." Each node is made up of two parts:

Details (which stores the information)

The pointer (which point the next element)

A linked list's items are linked via pointers, as demonstrated in the graphic below:

Ø TYPES OF LINKED LIST:

There are three alternative implementations of Linked List available:

1.    Singly Linked List

2.    Doubly Linked List

3.    Circular Linked List

Ø SINGLE LINK LIST

A single linked list is a series of elements in which each member is connected to the one after it in the sequence.

The address of the next node in the list is contained in each link component.

The address of the first node in a single linked list is always maintained in a reference node known as Start.

The last node's link has a NULL value, indicating that the node has come to an end.

 

u  OPERATION ON SINGLE LINK LIST:

·       Insertion: To add a node at the given position.

·       Deletion: To delete a node.

 

 

Insertion can be divided into the following categories:

     Case 1: Insert at the beginning

     Case 2: Insert at the end

     Case 3: Insert at specific location

 

Ø INSERT AT BEGINNING :

1. Create a head pointer and set it to NULL.

2. Make a new node with the provided data.

3. Point the new node to the head node.

4. Finally, make the newly created node the head node. 

 

Ø INSERT AT END :

 

1. Declare the head pointer and set it to NULL.

2. Make a new node with the provided data. Also, create a new node.

3. If the head node is NULL, the new node will be the head.

4. If the head node is not null, locate the last node and create it.

 

Ø Doubly Linked List

Each node in a doubly linked list has a data portion as well as two addresses, one for the previous node and one for the next node.

A link element named first and last appears in a Doubly Linked List.

Each link has a data field(s) as well as two link fields named next and previous.

Each link is connected to its next link via its next link.

Each link is linked to the one before it by utilising the link before it. 

Ø Operation on Double Linked list:

Insertion inserts an element at the start of the list.

Deletion removes an element from the list's beginning.

 

Insertion of a Node at beginning

 

Insertion of a Node at the end

 

 

Deletion at beginning

 

Deletion in doubly linked list at the end

 

 

 

Ø Circular Linked List:

Circular Linked List is a Linked List variant in which the first element points to the final element and the last element points to the first element. A circular linked list can be created from a singly linked list or a doubly linked list.

1.    Singly Linked List as Circular

2.    Doubly Linked List as Circular

Ø Singly Linked List as Circular

In a single linked list, the final node's next pointer points to the first node.

 

 

 

Ø Doubly Linked List as Circular:

In a doubly linked list, the final node's next pointer refers to the first node, and the first node's previous pointer points to the last node, making the list circular in both directions. 

 

Ø Applications of Linked Lists:

Linked lists are used to implement stacks, queues, graphs, and other data structures.

 

Linked lists allow you to insert entries at the start and end of the list.

 

We don't need to know the size of Linked Lists ahead of time.