Concept of Linked List Data Structure 2022 - Programmrs

 LINKED LIST

A linked list is a collection of elements called ‘nodes’ where each node consists of two parts:

• Info: Actual element to be stored in the list. It is called a data field.
• Next: one or more link that points to the next and previous node in the list. It is also called the pointer field.

• The link list is a dynamic structure i.e. it grows or shrinks depending on different operations performed. 
• The last node has some specified value called NULL as the next address which means the end of the list.
  

TYPES OF LINKED LIST

• Singly Linked List

It is the simplest type of linked list in which every node contains some data and a

pointer to the next node of the same data type. The node contains a pointer to

the next node means that the node stores the address of the next node in the

sequence. A single linked list allows the traversal of data only in one way.

• Doubly Linked List

A doubly linked list or a two-way linked list is a more complex type of linked list

which contains a pointer to the next as well as the previous node in sequence,

Therefore, it contains three parts are data, a pointer to the next node, and a

pointer to the previous node. This would enable us to traverse the list in the

backward direction as well.

• Circular Linked List

A circular linked list is that in which the last node contains the pointer to the first

node of the list. While traversing a circular liked list, we can begin at any node

and traverse the list in any direction forward and backward until we reach the

same node we started. Thus, a circular linked list has no beginning and no end.

• Doubly Circular Linked List

A Doubly Circular linked list or a circular two-way linked list is a more complex

type of linked list that contains a pointer to the next as well as the previous node

in the sequence. The circular doubly linked list does not contain null in the

previous field of the first node.

LINKED LIST OPERATIONS

• Traversal: Access each element stored in the linked list
• Insertion: Add new elements to the linked list
• Deletion: Delete elements from the linked list
• Searching: Locating node in the linked list
• Sorting: Sort the nodes of the linked list

Algorithm 

Insertion:

a. Insert at Head

It involves the insertion of the new element at the beginning of the linked list.

1. Create a node using the malloc function
• new node= (struct node*) malloc(sizeof(struct node));
2.  Assign data to the info field of the new node
• newnode->info=data
3. Set 
• newnode->next=NULL
4. if the head is NULL then set head=newnode and exit
• head=newnode
5.  otherwise.

•  Set next of new node to head
• new node->next=head
•  Set the head pointer to point to the new node
• head=newnode

      7. End

b. Insert at Tail

It involves the addition of a new element to the end of the linked list.

1. Create a node using the malloc function
• new node= (struct node*) malloc(sizeof(struct node));
2. Assign data to the info field of the new node
• new node->info=data
3. if the head is NULL then set head=newnode and exit
4.  Otherwise
• Set
• ptr=head
• Find the last node 
• while( ptr->next !=NULL)
• ptr=ptr->next
• Set 
• ptr->next=newnode

     6. End

c. Insert at Specified Position

It inserts a new element at the given position in the linked list.

1. Create a node using the malloc function
• new node= (struct node*) malloc(sizeof(struct node));
2. Assign data to the info field of the new node
• new node->info=data
3.  Enter the position of a node at which you want to insert a new node.
4.  Let the position be pos
5.  Set
• ptr=head
• for(i=0;i<pos-1;i++){
• ptr=ptr->next;
• if(ptr=NULL) }
• printf("position not found");
• return;}}
6.  Set
• newnode->next=ptr->next
7.  Set next of ptr to point to the new node
• ptr->next=newnode
8.  End

Deletion:

a. Deletion at Beginning

 It removes the element stored at the beginning of the list.

1. If (head==NULL) then 
• Display "Node not found" and Exit
2. Otherwise, store the address of the first node in the temporary variable ptr
• ptr=head
3.  Set head of the next node to head
• head=head->next
4.  Free the memory reserved by the temp variable
• free(ptr)
5.  End

b. Deletion at End

It deletes the element stored at the end of the linked list.

1.  If (head==NULL) then
•          Display "Node not found" Exit
2.  Otherwise if (head->next==NULL) Set
•         ptr=head
•          head=NULL
•          free(ptr)
3. Otherwise
• ptr=head
• while(ptr->next!=NULL)
• temp=ptr
• ptr=ptr->next
• temp->next=NULL
• free(ptr)
4. End

c. Deletion at the specified position

 

It deletes the element stored at the given position in the linked list.

1. If head=NULL 
• Display "Node not found" and Exit
2. Otherwise
•  Enter the position pos of the node to be deleted
•  If pos=0
•  Set ptr=head
• head=head->next
• free(ptr)
•  Otherwise
•  Set
• ptr=head
• for( i=0;i<pos;i++){ 
• temp=ptr
• ptr=ptr->next
• if(ptr==NULL){ Display "Not found"
• return }}
•  Set 
• temp->next=ptr->next
•  free(ptr)
3.  End
   

LINKED LIST UTILITY

Lists are one of the most popular and efficient data structures, with a wide range of implementation in every programming language like C, C++, Python, Java, and C#.

 Linked lists are a great way to learn how pointers and memory work. By practicing how to manipulate linked lists, you can prepare yourself to learn more advanced data structures like graphs and trees.

TIME COMPLEXITY

 

The time complexity for the operations performed on the linked list is:

Search    O(n) O(n)

Insert    O(1) O(1)

Deletion   O(1) O(1)

APPLICATIONS OF LINKED LIST

1. Dynamic memory allocation
2. In undoing the functionality of the software
3. Hash tables, Graphs
4. Polynomial Manipulation representation
5. Access to previous and next URL searched 
6. The songs in the Music Player are linked to the next and the previous song