Linked List

Linked list
Advantages and disadvantages
Types of linked lists
Singly linked list
Doubly linked list
Header linked lists
Applications of linked list
Algorithm to search a value
Example of LinkedList
Algorithm for inserting a node
single link list
Applications of Arrays
data in continuous memory
queues
stacks
beginning of a linked list
traversing a linked list
Algorithm for traversing
Grounded header linked list
Circular Header linked list

1. Linked list

2. Definition A linked list is a linear collection of data element. These data elements are called nodes, and they point to the next node by means of pointer. A linked list is a data structure which can be used to implement other data structures such as stack, queues trees and so on. A linked list is a sequence of nodes in which each node contains data field and pointer which points to the next node. Linked list are dynamic in nature that is memory is allocated as and when required.

3. Linked list

4. Each node is divided into two parts The first part contains the information /data. The second part contains the address of the next node. The last node will not have any next node connected to it, so it will be store a special value called Null. The Null pointer represents the end of the linked list. Start pointer represent the beginning of the linked list. If Start=Null then It means that the linked list is empty.

5. The self referential structure in a link list is as follows:

6. Advantages and disadvantages Advantages of linked list Linked list are dynamic data structure; that is, they can grow or shrink during the execution of the program. Linked list have efficient memory utilisation. Memory is allocated whenever it is required and it is de-allocated whenever it is no longer needed. Insertion and deletion is easier and efficient. Many complex applications can be easily carried out with the linked lists.

7. Disadvantages of linked list They consume more space because every node requires an additional pointer to store the address of the next node. Searching a particular element is the list is difficult and time consuming.

8. Types of linked lists Singly linked list Circular linked list Doubly linked list Header linked list

9. Array Vs Linked list Array

10. Memory Requirement is less in array

11. Insertion and deletion

12. Singly linked list A Singly linked list is the simplest type of linked list in which each node contains some information/data and only one pointer which points to the next node in the linked list. The traversal of data element in a single a linked list can be done only in one way.

13. Circular linked lists Circular linked lists are a type of singly linked list in which the address part of the last node will store the address of the first node, unlike in singly linked list in which the address part of the last node stores a unique value Null. While traversing a circular linked list we can begin from any node, because a circular linked list does not have a first or last node.

14. Doubly linked list Doubly linked list is also called a two way linked list, it is a special type of linked list which can point to the next node as well as the previous node in the sequence. In a doubly linked list each node is divided into three parts: the first part is called the previous pointer, which contains the address of the previous node in the list. The second part is called the information part, which contains the information of the node. The third part is called the next pointer, which contains the address of the succeeding node in the list.

15. Header linked lists Header linked list are a special type of linked list which always contain a special node, called the header node, at the beginning. This header node usually contains vital information about the linked list, like the total number of nodes in the list, whether the list is sorted or not and so on. There are two types of header linked lists, which includes: Grounded header linked list Circular Header linked list.

16. Applications of linked list Polynomial manipulation representation Addition of long positive integers Representation of sparse matrix Linked application of Files

17. Algorithm for traversing a linked list Step 1: set PTR = Start Step 2: Repeat steps 3 & 4 while PTR != NULL Step 3 : Print PTR —>INFO Step 4: set PTR= PTR—> NEXT [end of loop] Step 5: exit

18. Algorithm to search a value in a linked list Step 1: Set PTR=Start Step 2: Repeat step3 while PTR !=NULL Step 3: If Search_Val =PTR—>INFO Set POS=PTR Print successful search Go to step 5 [end of if] Else Set PTR=PTR  NEXT [end of loop] Step 4: print unsuccessful search Step 5: exit

19. Example

20. Algorithm for inserting a new node in the beginning of a linked list Step 1: Start Step 2: IF PTR=NULL print overflow Go to step 8 [end of IF] Step 3: Set NEW NODE=PTR Step 4: set PTR=PTR—>NEXT Step 5: set NEW NODE—>INFO =Value Step 6: Set NEW NODE—>NEXT=START Step 7: Set START =NEW NODE Step 8:exit

21. */single link list*/ #include<stdio.h> #include<stdlib.h> struct node {Int data; struct node* link; }; struct node *root=NULL; void main() { Int ch; while(1) { printf(‘single linked list operations: \n”); Printf(“1.append\n”); Printf(‘2 addafter\n”); Printf(“enter your choice :”); Scanf(“%d”,&ch); Switch(ch) {case 1:append(); Break; } }

22. Void append() { struct node *temp; temp=(struct node*)malloc(sizeof(struct node)); Printf(“enter node data : “); Scanf(“%d”, &temp—>data); temp—->link=NULL; If(root==NULL) { root=temp; } else { Struct node *p; p=root; While(p—>link!=Null) {p=p—>link; } p->link=temp; } }

23. Applications of Arrays Arrays are very useful in storing the data in continuous memory locations. Arrays are used for implementing various other data structures such as stacks,queues etc. Arrays are very useful as we can perform various operation on them.