Skip to main content

Linear Data Structure Algorithm: Part II


Linked List is another variation of Linear Data Structure. Though it is categorized in Linear Data Structure, it is not contiguous in nature. Rather it stores nodes in different locations at memory and links the nodes to each other forming a list, Therefore derives the name Linked List.

Single Linked List

Algorithm to create a node in Single Linked List:

Allocate memory for ptr (pointer to new node)
If ptr = NULL
    print: Overflow: Memory not allocated
End If
   
Read Data to be inserted in node
Set nptr->info = data
Set nptr->next = NULL
   
return nptr
End


Algorithm to Count Node in Linked List:


Set count to 0
Set temp to First
While temp != NULL
    Set count = count + 1
    Set temp = temp->next
End While
return count
End


Algorithm to Reverse a given Linked List:


reverse(First)
   Set temp = First
   Set ptr = NULL
   Set ptemp = NULL
   While temp != NULL
       Set ptemp = ptr
       Set ptr = temp
       temp = temp->next
       Set ptr->next = ptemp
E   end While
   Set First = ptr
End


Algorithm to Insert node at Beginning in Simple Linked List


insertBeg(First)
   create node(refer create node algorithm)
   Set nptr->next = First
   Set First=nptr
End


Algorithm to Insert node at End in Simple Linked List


insert_end(First)
   create node(refer create node algorithm)
   If First = NULL
       Set First = nptr
   Else
       Set temp = First
       While temp->next != NULL
           Set temp = temp->next
    E end While
       Set temp->next = nptr
   End If
End


Algorithm to Insert at Given Position in Simple Linked List


insertPos(First)
   create node(refer create node algorithm)
   Set temp = First
   Read pos
   call count node algorithm
   If pos > count + 1 OR pos = 0
       Print: Invalid position
       return
   End If
   If pos = 1
       Set nptr->next = First
       Set First = nptr 
   Else
       Set i = 1
       While i < pos - 1
           Set temp = temp->next
           Set i = i + 1
    E end While
       Set nptr->next = temp->next
       Set temp->next = nptr
   End If
End


Algorithm to Delete node at Beginning in Simple Linked List


deleteBeg(First)
If First = NULL
    Print: List is Empty
End If
Set temp = First
Set First = First->next
Free temp
End


Algorithm to Delete node at End in Single Linked List


deleteEnd(First)
If First = NULL
    Print: List is Empty
End If
Set temp = First
If temp->next = NULL
    Set First = NULL
Else
    While temp->next != NULL
        Set ptemp = temp
        Set temp = temp->next
    End While
End If
Set save->next = NULL
Free temp
End


Algorithm to Delete Node at a Given position in Single Linked List


deletePos(First)
If First = NULL
    Print: List is Empty
End If
Set temp = First
Read pos
Call count //refer count algorithm in Single Linked List section

If pos > count + 1 OR pos = 0
    Print: Invalid Position
    return
End If
If pos = 1
    Set First = temp->next
Else
    Set i = 1
    While i < pos
        Set ptemp = temp
        Set temp = temp->next
        Set i = i + 1
    End While
    Set ptemp->next = temp->next
End If
Free temp
End


Algorithm for Display in Linked List

display()
Set ptr to head;    //start from the beginning
While ptr != NULL
       Print: ptr->key,ptr->data 
       ptr = ptr->next
End While
End


Circular Linked List

Algorithm to Insert a node at Beginning in circular linked list:

insertBeg(First)
create node     //refer create node algorothm in Single Linked List Section
If First = NULL
    Set First = nptr
    Set First->next = First
Else
    Set temp = First
    While temp->next != First
        Set temp = temp->next
    End While
    Set nptr->next = First
    Set First = nptr
    Set temp->next = First
End If
End


Algorithm to Insert a node at end in Circular Linked List:


insertEnd(First)
create node     //refer create node algorothm in Single Linked List Section
If First = NULL
    Set First = nptr
    Set First->next = First
Else
    Set temp = First
    While temp->next != First
        Set temp = temp->next
    End While
    Set temp->next = nptr
    Set nptr->next = First
End If
End


Algorithm for Delete Node at Beginning in circular linked list:


deleteBeg(First)
If First = NULL
    Print: List is Empty and return
End If
Set temp = First
Set ptr = temp
While ptr->next != First
    Set ptr = ptr->next
End While
Set First = First->next
Set ptr->next = First
Free temp
End


Algorithm to Delete Node at end in circular linked list:


deleteBeg(First)
If First = NULL
    Print: List is Empty and return
End If

Set temp = First
If temp->next = First
    Set First = NULL
Else
    While temp->next != First
        Set ptemp = temp
        Set temp = temp->next
    End While
    Set ptemp->next = First
End If
Free temp
End


Algorithm for Display circular linked list:    

display(First) 
If First = NULL
    Print: List is Empty
End If
Set temp = First
While temp != First
    Print temp->info
    Set temp = temp->next
End While
End


Algorithm to create a Doubly Linked List Node

Allocate memory for nptr
If nptr = NULL
    Print: Memory not allocated
End If
Read data
Set nptr->info = data
Set nptr->prev = NULL
Set nptr->Next = NULL
return nptr
End


Algorithm for Display circular linked list:

display(First) 
If First = NULL
    Print: List is Empty
End If
Set temp = First
While temp != First
    Print temp->info
    Set temp = temp->next
End While
End


Doubly linked List

Algorithm to create a Doubly Linked List Node

Allocate memory for nptr
If nptr = NULL
    Print: Memory not allocated
End If
Read data
Set nptr->info = data
Set nptr->prev = NULL
Set nptr->Next = NULL
return nptr
End



Algorithm for Insertion at front doubly linked list:

//insert link at the first location 
InsertFirst(int key, int data)

//create a link 
struct node *link = (struct node*) malloc(sizeof(struct node))
link->key = key 
link->data = data

If(isEmpty())  
    //make it the last link 
    last = link 
Else
    //update first prev link  
    head->prev = link 
End If

//point it to old first link
link->next = head 
//point first to new first link 
head = link



Algorithm for deletion at front end doubly linked list


//delete first item
struct node*deleteFirst()

//save reference to first link 
struct node *tempLink = head 
//if only one link 
if(head->next == NULL)
    last = NULL
Else
    head->next->prev = NULL 
Else If
    head = head->next
End If  

//return the deleted link
return tempLink

End


Algorithm for Insertion at end:


//insert link at the last location 
InsertLast(int key, int data) 

//create a link
Allocate memory to node  
link->key = key 
link->data = data 
if(isEmpty()) 
    //make it the last link
    last = link  
Else 
    //make link a new last link 
    last->next = link 
    //mark old last node as prev of new link 
    link->prev = last
End If 
//point last to new last node 
last = link

End


Algorithm for deletion at end Doubly ll:


//save reference to last link 
struct node *tempLink = last 

//if only one link
if(head -> next == NULL)
    head = NULL
Else
    last -> prev -> next = NULL
End If

last = last -> prev
//return the deleted link  
return tempLink

End

Comments

Post a Comment

Popular posts from this blog

Tree and Graph Tree and graph can be classified under the non linear data structure. Here I have shared few algorithms of tree and graph. Graph algorithms Algorithm for DFS(Depth First Search) graph traversal: Step 1:Define a Stack of size total number of vertices in the graph. Step 2:Select any vertex as starting point for traversal.Visit that vertex and push it on to the Stack. Step 3:Visit any one of the adjacent vertex of the vertex which is at top of the stack which is not visited and push it on to the stack. Step 5:When there is no new vertex to be visit then use back tracking and pop one vertex from the stack. Step 6:Repeat steps 3, 4 and 5 until stack becomes Empty. Step 7:When stack becomes Empty, then produce final spanning tree by removing unused edges from the graph. Algorithm for BFS(Breadth First Search) graph traversal: Step 1:Define a Queue of size total number of vertices in the graph. Step 2:Select any vertex as starting point for traversal.Visit ...
Post a Comment
Read more
Linear Data Structure Algorithm - Part I Hello all you young hearts! "You are never given a wish without also being given a power to make it come true. You may have to work for it however." -Richard David Bach Here is my blog that gives you information about various algorithm of Data Structure. In this blog I have shared information about Linear Data Structure. Linear Data Structure includes Stack, Queue and Linked List. This blog basically focuses on Stack and Queue. Stack Algorithms Algorithm for Push operation: If(top>size-1)     Print Stack is full Else     Top=top+1     a[top]=item     Print a[top] is added End If  Algorithm for Pop operation: If(top is less than 0)     Print Stack is empty Else     a[top]=item     Top=top-1     Print a[top] is deleted End If Algorithm for Peek operation If(top is less than 0)  ...
2 comments
Read more