/* Ajith - Syntax Higlighter - End ----------------------------------------------- */
Showing posts with label Linked List. Show all posts
Showing posts with label Linked List. Show all posts

3.13.2013

Checking Balance of Symbols in a expression

This article is part of article series - "Datastructures"

A balanced expression contains right number of closing and open braces.

For example:

  • [[ - unbalanced expression
  • []{}() - balanced expression
  • [(*)] - balanced expression

Let us see how to find if an expression is balanced or not by checking for following operators [ ] { } and ( ) in the given expression.

Using Stacks



2.05.2013

Conversion from Infix to Postfix

This article is part of article series - "Datastructures"

Converting a Fully Parenthesized Infix expression into Postfix expression  


Analysis:

Five types of input characters

  • Opening parentheses
  • Operands
  • Operators
  • Closing parentheses
  • New line character (\n)

Pseudocode:


********************************************************  
 Function  : main  
  
 Calls     : createStack  
             freeStack                
             pushIntoStack   
             popFromStack   
  
 Called by : NONE   
  
 Input   
 Parameters: Accepts input expression for processing  
    
 Returns   : Converts Fully paranthesized INFIX 
             expression into POSTFIX expression
******************************************************** 

SET i to 0
GET infix expression from user into input_array
SET var with input_array[i]

CALL createStack

WHILE var != end of string

  IF var equals to '(' THEN
  
    CALL pushIntoStack (stack, var)  

  ELSE IF var is a number THEN        
  
    PRINT var  

  ELSE IF var is an arithmetic operator THEN
  
    CALL pushIntoStack (stack, var) 
    
  ELSE IF var equals to ')' THEN

    WHILE stackTop != '('

      IF stackTop is an arithmetic operator THEN

        PRINT stackTop
        popFromStack (stack)

      ENDIF
    
    ENDWHILE

    popFromStack (stack)

  ENDIF

  SET var with input_expression[INCREMENT i]

ENDWHILE

CALL freeStack (stack)

12.25.2012

Deleting a Node from a Singly Linked List

This article is part of article series - "Datastructures"

Previous Article: Implementation of Singly Linked List.
Next Article: Reversing a Singly Linked List

Deletion of a Node from a Singly Linked List
Similar to insertion we have three cases for deleting a Node from a Singly Linked List.

  • Deleting First Node in Singly Linked List

    To complete deletion of firstNode in the list we have to change Head pointing to Next of firstNode.

    Pseudocode:
    firstNode = Head
    
    Head = firstNode->Next
    
    free firstNode
    Complexity:
    Time Complexity: O(1)
    Space Complexity: O(1)

Detecting First Node in a Loop in the List

This article is part of article series - "Datastructures"

Previous Article: Detecting a Loop in Singly Linked List - Tortoise and Hare.
Next Article: Finding Nth node from end of a Singly Linked List.

Once we confirm that there is a Loop in a Singly Linked List we will see how to determine first node of the loop.


11.13.2012

Finding Nth node from end of a Singly Linked List

This article is part of article series - "Datastructures"

Previous Article: Finding first node in a Loop in Singly Linked List.

Figure 1: Singly Linked List

Solution 01 - Brute Force Approach:
  1. Start at First Node of the List (call it curNodePtr).
  2. Assign curNodePtr to tmpPtr and count number of nodes after the curNodePtr.
  3. If number of nodes after curNodePtr are equal to N nodes or tmpPtr reaches END then break. If tmPtr reaches END but count not equal to N then return since we can't find the Nth node from the end of the Singly Linked List.
  4. Move the curNodePtr one step forward in the Linked List i.e curNodePtr now points to its next node in the list and start again from STEP-2.

11.06.2012

Reversing a Singly Linked List

This article is part of article series - "Datastructures"

Previous Article: Deleting a Node from a Singly Linked List.
Next Article: Detecting a Loop in Singly Linked List - Tortoise and Hare.

Let us see how to reverse a Singly Linked List.

Figure-1: Singly Linked List
Pseudocode:
cur_ptr = HEAD->NEXT
prev_ptr = NULL

forever:

   if cur_ptr == NULL
   break

   tmp_ptr  = prev_ptr
   prev_ptr = cur_ptr
   cur_ptr  = cur_ptr->NEXT
   
   prev_ptr->NEXT = tmp_ptr

HEAD->NEXT = prev_ptr
Complexity:
Time Complexity: O(n)
Space Complexity: O(3)

If we try on the example in Figure-1 we get the output as shown below

Figure-2: After reversing the Singly Linked List


Previous Article: Deleting a Node from a Singly Linked List.
Next Article: Detecting a Loop in Singly Linked List - Tortoise and Hare.

9.21.2012

Detecting a Loop in Singly Linked List - Tortoise & Hare

This article is part of article series - "Datastructures"

Previous Article: Reversing a Singly Linked List.
Next Article: Finding first node in a Loop in Singly Linked List.

Eventhough there are multiple algorithms available we start with

Floyd's Cycle-Finding Algorithm
In simple terms it is also known as "Tortoise and Hare Algorithm" or "Floyd's Cycle Detection Algorithm" named after its inventor Robert Floyd. It is one of the simple cycle detection algorithm. It's a simple pointers based approach.

Robert Floyd

3.01.2012

Deletion of a Node from Doubly Linked List

This article is part of article series - "Datastructures".

Previous Article: Inserting a Node in Doubly Linked List.

Deletion of a Node 
Let us say our current Doubly Linked List is as shown in Figure-1.
Figure 1: Current Doubly Linked List

  • Deleting First Node of the List
  • Now we have to delete First Node from the List shown in Figure-1. Because of this operation HEAD and Node-2 are affected.
    In HEAD - FIRST variable should now point to NODE-2 (i.e HEAD->FIRST = HEAD->FIRST->NEXT). If you see HEAD->FIRST->NEXT actually HEAD->FIRST currently points to NODE-1 so HEAD->FIRST->NEXT is equivalent to NODE-1->NEXT which is NODE-2.
    In NODE-2 - NEXT variable remains unchanged and PREV variable should now point to NULL since it is the first Node in the List.
    Decrement LENGTH variable in HEAD so that it maintains proper count of Nodes in the List.
    Pseudocode:
    HEAD->FIRST = HEAD->FIRST->NEXT
    
    NODE-2->PREV = NULL
    
    decrement(HEAD->LENGTH)
    Output:
Figure 2: After deleting the First Node in the List.

2.27.2012

Inserting a Node in Doubly Linked List

This article is part of article series - "Datastructures"

Previous Article: Doubly Linked List                                           Next Article: Deletion of a Node from Doubly Linked List.

Insertion of a Node
Before we discuss about how to insert a NODE let us discuss few rules to follow at the time of insertion.

  • Check the location into which the user want to insert a new NODE. The possible locations where an user can insert a new node is in the range of 1 <= loc <= (length of list)+1. Let us say the length of the list is 10 & the user want to insert at location 12 (sounds stupid).

  • As we know we can traverse Bi-Directional in case of Doubly Linked Lists so we have to take care of PREV and NEXT variables in the NODE structure. We should also update the neighboring Nodes which are affected by this operation. If not we might break up the List somewhere or the other by creating a BROKEN LIST.

We have following scenarios in the case of insertion of a NODE.
  • Adding a Node at the start of the Empty List
  • Figure 1: Empty List and the newNode we want to add
    As shown in Figure-1 we have a Empty List with LENGTH set to 0 and FIRST pointing to NULL. Let us add newNode at Location 1. 
    In HEAD - FIRST variable points to newNode (head->FIRST = newNode).
    In newNode - NEXT and  PREV points to NULL as we don't have any other Nodes in the List.
    Increment the LENGTH variable in HEAD once insertion is successful to maintain the count of number of Nodes in the List.
    Pseudocode:
    HEAD->FIRST = newNode
    
    newNode->PREV = NULL
    
    newNode->NEXT = NULL
    
    increment(HEAD->LENGTH)
    Output:
Figure 2: After adding newNode in Empty List. (Changes in BLUE)

2.24.2012

Implementation of Doubly Linked List in C

In computer science, a doubly linked list is a linked data structure that consists of a set of sequentially linked records called Nodes. Each Node contains two fields, called Links, that are references to the Previous and to the Next Node in the sequence of Nodes as well as field named Data.
For every Linked List we have something called Head which marks the starting of a list. So we have two main structures namely
  • Node
  • Head

Why we need a new structure for HEAD variable ? 
Just for convenience I decided to have HEAD its own structure. You can even use the Node structure.

Node
Every Node in a Doubly Linked List has three main members namely
  • PREV
  • DATA
  • NEXT
As their names say
  • PREV - holds the memory location of the Previous Node in the List. If there are none we point towards NULL. For the First Node in the List PREV points to NULL.
  • NEXT - holds the memory location of the Next Node in the List. If there are none we point towards NULL. For the Last Node in the List NEXT points to NULL.
  • DATA - In simple words it holds Data. In our case it holds the memory location to the actual data to be held by the Node.
typedef struct node
{
    struct node *prev;
    void        *data;
    struct node *next;
}NODE;

Head
Head acts as the  "head" of the List. Head structure has two members namely
  • LENGTH - holds the count of number of Nodes in the List.
  • FIRST - hold the memory location of the first Node in the List. If the List is EMPTY it points to NULL.
typedef struct head 
{
    unsigned int length;
    struct node  *first;
}HEAD;

NOTE: Our Head structure doesn't contain any pointer to the Tail of the List. Eventhough its a best way to include a pointer to Tail Node we decided to cover that implementation in Circular Doubly Linked List.

7.07.2010

Implementation of Stack using Singly Linked Lists

Stacks are linear data structures which means the data is stored in what looks like a line (although vertically). In simple words we can say
A stack is a last in, first out (LIFO) abstract data type and data structure.
Basic usage of stack at the Architecture level is as a means of allocating and accessing memory.


We can only perform two fundamental operations on a stack: push and pop.

The push operation adds to the top of the list, hiding any items already on the stack, or initializing the stack if it is empty. The pop operation removes an item from the top of the list, and returns this value to the caller. A pop either reveals previously concealed items, or results in an empty list.

A stack is a restricted data structure, because only a small number of operations are performed on it.

4.24.2010

Singly Linked List in C

Check Implementation of Singly Linked List for theoretical explanation regarding implementation of singly linked lists.

  #include <stdio.h>
#include <stdlib.h>

//Structure containing a Data part & a
//Link part to the next node in the List

struct Node
{
 int Data;
 struct Node *Next;
}*Head;

// Counting number of elements in the List

int length()
{
  struct Node *cur_ptr;
  int count=0;

  cur_ptr=Head;

  while(cur_ptr != NULL)
  {
     cur_ptr=cur_ptr->Next;
     count++;
  }
  return(count);
}

// Deleting a node from List depending upon the data in the node.

int delNodeData(int num)
{
  struct Node *prev_ptr, *cur_ptr;

  cur_ptr=Head;

  while(cur_ptr != NULL)
  {
     if(cur_ptr->Data == num)
     {
        if(cur_ptr==Head)
        {
           Head=cur_ptr->Next;
           free(cur_ptr);
           return 0;
        }
        else
        {
           prev_ptr->Next=cur_ptr->Next;
           free(cur_ptr);
           return 0;
        }
     }
     else
     {
        prev_ptr=cur_ptr;
        cur_ptr=cur_ptr->Next;
     }
  }

  printf("\nElement %d is not found in the List", num);
  return 1;
}

// Deleting a node from List depending upon the location in the list.

int delNodeLoc(int loc)
{
  struct Node *prev_ptr, *cur_ptr;
  int i;

  cur_ptr=Head;

  if(loc > (length()) || loc <= 0)
  {
      printf("\nDeletion of Node at given location is not possible\n ");
  }
  else
  {
      // If the location is starting of the list
      if (loc == 1)
      {
          Head=cur_ptr->Next;
          free(cur_ptr);
          return 0;
      }
      else
      {
          for(i=1;i<loc;i++)
          {
              prev_ptr=cur_ptr;
              cur_ptr=cur_ptr->Next;
          }

          prev_ptr->Next=cur_ptr->Next;
          free(cur_ptr);
      }
  }
  return 1;
}

//Adding a Node at the end of the list

void addEnd(int num)
{
  struct Node *temp1, *temp2;

  temp1=(struct Node *)malloc(sizeof(struct Node));
  temp1->Data=num;

  // Copying the Head location into another node.
  temp2=Head;

  if(Head == NULL)
  {
     // If List is empty we create First Node.
     Head=temp1;
     Head->Next=NULL;
  }
  else
  {
     // Traverse down to end of the list.
     while(temp2->Next != NULL)
     temp2=temp2->Next;

     // Append at the end of the list.
     temp1->Next=NULL;
     temp2->Next=temp1;
  }
}

// Adding a Node at the Beginning of the List

void addBeg(int num)
{
  struct Node *temp;

  temp=(struct Node *)malloc(sizeof(struct Node));
  temp->Data = num;

  if (Head == NULL)
  {
     //List is Empty
     Head=temp;
     Head->Next=NULL;
  }
  else
  {
     temp->Next=Head;
     Head=temp;
  }
}

// Adding a new Node at specified position

void addAt(int num, int loc)
{
  int i;
  struct Node *temp, *prev_ptr, *cur_ptr;

  cur_ptr=Head;

  if(loc > (length()+1) || loc <= 0)
  {
     printf("\nInsertion at given location is not possible\n ");
  }
  else
  {
      // If the location is starting of the list
      if (loc == 1)
      {
          addBeg(num);
      }
      else
      {
          for(i=1;i<loc;i++)
          {
              prev_ptr=cur_ptr;
              cur_ptr=cur_ptr->Next;
          }

          temp=(struct Node *)malloc(sizeof(struct Node));
          temp->Data=num;

          prev_ptr->Next=temp;
          temp->Next=cur_ptr;
      }
  }
}

// Displaying list contents

void display()
{
  struct Node *cur_ptr;

  cur_ptr=Head;

  if(cur_ptr==NULL)
  {
     printf("\nList is Empty");
  }
  else
  {
      printf("\nElements in the List: ");
      //traverse the entire linked list
      while(cur_ptr!=NULL)
      {
          printf(" -> %d ",cur_ptr->Data);
          cur_ptr=cur_ptr->Next;
      }
      printf("\n");
  }
}

//Reversesing a Linked List

void reverse()
{
  struct Node *prev_ptr, *cur_ptr, *temp;

  cur_ptr=Head;
  prev_ptr=NULL;

  while(cur_ptr != NULL)
  {
     temp=prev_ptr;
     prev_ptr=cur_ptr;

     cur_ptr=cur_ptr->Next;
     prev_ptr->Next=temp;
  }

  Head=prev_ptr;
}


int main(int argc, char *argv[])
{
 int i=0;

 //Set HEAD as NULL
 Head=NULL;

 while(1)
 {
    printf("\n####################################################\n");
    printf("MAIN MENU\n");
    printf("####################################################\n");
    printf(" \nInsert a number \n1. At the Beginning");
    printf(" \n2. At the End");
    printf(" \n3. At a Particular Location in the List");
    printf(" \n\n4. Print the Elements in the List");
    printf(" \n5. Print number of elements in the List");
    printf(" \n6. Reverse the linked List");
    printf(" \n\nDelete a Node in the List");
    printf(" \n7. Delete a node based on Value");
    printf(" \n8. Delete a node based on Location\n");
    printf(" \n\n9. Exit\n");
    printf(" \nChoose Option: ");
    scanf("%d",&i);

    switch(i)
    {
      case 1:
      {
          int num;
          printf(" \nEnter a Number to insert in the List: ");
          scanf("%d",&num);
          addBeg(num);
          display();
          break;
      }

      case 2:
      {
          int num;
          printf(" \nEnter the Number to insert: ");
          scanf("%d",&num);
          addEnd(num);
          display();
          break;
      }

      case 3:
      {
          int num, loc;
          printf("\nEnter the Number to insert: ");
          scanf("%d",&num);
          printf("\nEnter the location Number in List at which \
          the Number is inserted: ");
          scanf("%d",&loc);
          addAt(num,loc);
          display();
          break;
      }

      case 4:
      {
          display();
          break;
      }

      case 5:
      {
          display();
          printf(" \nTotal number of nodes in the List: %d",length());
          break;
      }

      case 6:
      {
          reverse();
          display();
          break;
      }

      case 7:
      {
          int num;
          printf(" \nEnter the number to be deleted from List: ");
          scanf("%d",&num);
          delNodeData(num);
          display();
          break;
      }

      case 8:
      {
          int num;
          printf(" \nEnter the location of the node to \
          be deleted from List: ");
          scanf("%d",&num);
          delNodeLoc(num);
          display();
          break;
      }

      case 9:
      {
          struct Node *temp;

          while(Head!=NULL)
          {
              temp = Head->Next;
              free(Head);
              Head=temp;
          }
          exit(0);
      }

      default:
      {
          printf("\nWrong Option choosen");
      }
    }/* end if switch */
 }/* end of while */
}/* end of main */

8.26.2009

Implementation of Singly Linked List

This article is part of article series - "Datastructures"

Generally a Linked List means "Singly Linked List". It is a chain of records known as Nodes. Each node has at least two members, one of which points to the next Node in the list and the other holds the data.

Figure 1: Singly Linked List
Basically Single Linked Lists are uni-directional as they can only point to the next Node in the list but not to the previous. We use below structure for a Node in our example.
 struct Node
 {
   int Data;
   struct Node *Next;
 }; 
Variable Data holds the data in the Node (It can be a pointer variable pointing to the dynamically allocated memory) while Next holds the address to the next Node in the list.

Figure 2: Node in a Singly Linked List
Head is a pointer variable of type struct Node which acts as the Head to the list. Initially we set 'Head' as NULL which means list is empty.