two way linked list

how can I change from the single linked to two way linked list in c

Page 1 of 1

3 Replies - 15537 Views - Last Post: 28 August 2009 - 06:15 AM Rate Topic: -----

#1 karthikumar   User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 2
  • Joined: 28-August 09

two way linked list

Posted 28 August 2009 - 05:09 AM

/* CH4PR1.C: Program to maintain a linked list */

#include <stdio.h>
#include <malloc.h>

/* structure containing a data part and link part */
struct node
{
	int data;
	struct node * link;
};

void append ( struct node **, int );
void addatbeg ( struct node **, int );
void addafter ( struct node *, int, int );
void display ( struct node * );
int count ( struct node * );
void delete ( struct node **, int );

int main( )
{
	struct node *p;
	p = NULL;  /* empty linked list */
		int n,a,l,d=1;
		printf("\n   PROGRAM USING LINKED LIST ");
	  while(d==1)
	   {
		printf("\n\n  View the operations that can be performed. ");
		printf("\n\n\t1.Append\n\t2.Add at the begining\n\t3.Add after\n\t4.Display\n\t5.Count\n\t6.Delete\n   Now enter your choice :");
		scanf("%d",&n);
	printf ( "\nNo. of elements in the Linked List = %d", count ( p ) );
	switch(n)
		 {
		   case 1:
				  {
				   printf("\n  Enter the value to append  :");
				   scanf("%d",&a);
				   append ( &p,a );
	/*append ( &p, 30 );
	append ( &p, 25 );
	append ( &p, 42 );
	append ( &p, 17 );*/
				   break;
				  }
		   case 4:
				{
				 display ( p );
				 break;
				}
		   case 2:
				  {
					printf("\n  Enter the number to add at the begining  :");
				scanf("%d",&a);
					 addatbeg ( &p,a );
	/*addatbeg ( &p, 888 );
	addatbeg ( &p, 777 );

	display ( p );*/
					break;
				   }
		   case 3:
				  {
				   printf("\n   Enter the number to add  :");
				   scanf("%d",&a);
				   printf("\n   Enter the location :");
				   scanf("%d",&l);
			   addafter ( p, l, a );
	/*addafter ( p, 2, 1 );
	addafter ( p, 5, 99 );

	display ( p );
	printf ( "\nNo. of elements in the Linked List = %d", count ( p ) );*/
				   break;
				  }
			case 6:
				  {
				   printf("\n  Enter the number to delete  :");
				   scanf("%d",&a);
				   delete ( &p, a );
				   break;
				  }
	/*delete ( &p, 1 );
	delete ( &p, 10 );

	display ( p );*/
			case 5:
				   {
					printf ( "\nNo. of elements in the Linked List = %d", count ( p ) );
					break;
				   }
			default:
				   {
					printf("\n  Sorry. Invalid iput...");
				   }
		  }  
			printf("\n  Do you want to continue (1/0)?  :");
			scanf("%d",&d);
}		  
		return 0;
}

/* adds a node at the end of a linked list */
void append ( struct node **q, int num )
{
	struct node *temp, *r;

	if ( *q == NULL ) /* if the list is empty, create first node */
	{
		temp =(struct node*)malloc ( sizeof ( struct node ) );
		temp -> data = num;
		temp -> link = NULL;
		*q = temp;
	}
	else
	{
		temp = *q;

		/* go to last node */
		while ( temp -> link != NULL )
			temp = temp -> link;

		/* add node at the end */
		r = ( struct node*)malloc ( sizeof ( struct node ) );
		r -> data = num;
		r -> link = NULL;
		temp -> link = r;
	}
}

/* adds a new node at the beginning of the linked list */
void addatbeg ( struct node **q, int num )
{
	struct node *temp;

	/* add new node */
	temp = malloc ( sizeof ( struct node ) );

	temp -> data = num;
	temp -> link = *q;
	*q = temp;
}

/* adds a new node after the specified number of nodes */
void addafter ( struct node *q, int loc, int num )
{
	struct node *temp, *r;
	int i;

	temp = q;
	/* skip to desired portion */
	for ( i = 0; i < loc; i++ )
	{
		temp = temp -> link;

		/* if end of linked list is encountered */
		if ( temp == NULL )
		{
			printf ( "\nThere are less than %d elements in list", loc );
			return;
		}
	}

	/* insert new node */
	r = ( struct node* ) malloc ( sizeof ( struct node ) );
	r -> data = num;
	r -> link = temp -> link;
	temp -> link = r;
}

/* displays the contents of the linked list */
void display ( struct node *q )
{
	printf ( "\n" );

	/* traverse the entire linked list */
	while ( q != NULL )
	{
		printf ( "%d ", q -> data );
		q = q -> link;
	}
}

/* counts the number of nodes present in the linked list */
int count ( struct node * q )
{
	int c = 0;

	/* traverse the entire linked list */
	while ( q != NULL )
	{
		q = q -> link;
		c++;
	}

	return c;
}

/* deletes the specified node from the linked list */
void delete ( struct node **q, int num )
{
	struct node *old, *temp;

	temp = *q;

	while ( temp != NULL )
	{
		if ( temp -> data == num )
		{
			/* if node to be deleted is the first node in the linked list */
			if ( temp == *q )
				*q = temp -> link;

			/* deletes the intermediate nodes in the linked list */
			else
				old -> link = temp -> link;

			/* free the memory occupied by the node */
			free ( temp );
			return;
		}

		/* traverse the linked list till the last node is reached */
		else
		{
			old = temp;  /* old points to the previous node */
			temp = temp -> link;  /* go to the next node */
		 }
	}

	printf ( "\nElement %d not found", num );
}

***added code tags -jjsaw5***

Is This A Good Question/Topic? 0
  • +

Replies To: two way linked list

#2 jjsaw5   User is offline

  • D.I.C Lover
  • member icon

Reputation: 92
  • View blog
  • Posts: 3,063
  • Joined: 04-January 08

Re: two way linked list

Posted 28 August 2009 - 05:21 AM

:code:


Please post your question or issue.
Was This Post Helpful? 0
  • +
  • -

#3 Ancient Dragon   User is offline

  • D.I.C Addict
  • member icon

Reputation: 82
  • View blog
  • Posts: 679
  • Joined: 19-July 09

Re: two way linked list

Posted 28 August 2009 - 05:45 AM

>> how can I change from the single linked to two way linked list in c

Add another pointer named prev to the structure, which points to the node just preceeding the current node, or to the lists tail if the current node is the head. Then when you add or delete a node you have to adjust this prev pointer as well as the next pointer.

Also I would change the name link to next to make it more descriptive of what that pointer does.

This post has been edited by Ancient Dragon: 28 August 2009 - 05:46 AM

Was This Post Helpful? 0
  • +
  • -

#4 baavgai   User is online

  • Dreaming Coder
  • member icon


Reputation: 7267
  • View blog
  • Posts: 15,146
  • Joined: 16-October 07

Re: two way linked list

Posted 28 August 2009 - 06:15 AM

Completely agree with dragon. Also, and this is more of a style preferance, having a list struct and a couple of type defs can make code easier to deal with.

e.g.
typedef struct NodeStruct {
	int data;
	struct NodeStruct *prev, *next;
} Node;

typedef struct {
	Node *head;
} List;

void append ( List *, int );


Was This Post Helpful? 0
  • +
  • -

Page 1 of 1