********************************************************
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)
firstNode = Head Head = firstNode->Next free firstNodeComplexity:
 |
| Figure 1: Singly Linked List |
 |
| Figure-1: Singly Linked List |
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_ptrComplexity:
 |
| Figure-2: After reversing the Singly Linked List |
 |
| Robert Floyd |
 |
| Figure 1: Current Doubly Linked List |
HEAD->FIRST = HEAD->FIRST->NEXT NODE-2->PREV = NULL decrement(HEAD->LENGTH)Output:
 |
| Figure 2: After deleting the First Node in the List. |
 |
| Figure 1: Empty List and the newNode we want to add |
HEAD->FIRST = newNode newNode->PREV = NULL newNode->NEXT = NULL increment(HEAD->LENGTH)
 |
| Figure 2: After adding newNode in Empty List. (Changes in BLUE) |
typedef struct node
{
struct node *prev;
void *data;
struct node *next;
}NODE;
typedef struct head
{
unsigned int length;
struct node *first;
}HEAD;
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.
#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 */
 |
| Figure 1: Singly Linked List |
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 |