• Hey, guest user. Hope you're enjoying NeoGAF! Have you considered registering for an account? Come join us and add your take to the daily discourse.

Linked Lists in C

Status
Not open for further replies.
P

peppermints

Member
I'm having some trouble wrapping my head around linked lists in C... I have a basic program made that creates a linked list, allows you to add nodes, delete nodes, etc:

Code: 
struct link
{
	int item;
	struct link *next;
};
typedef struct link node;

node *head=NULL;

void addfirst()
{
	node *temp;
	temp=(node *)malloc(sizeof(node));
	printf("Enter the data....\t");
	scanf("%d",&temp->item);
	temp->next=head;
	head=temp;
}

void addend()
{
	node *temp,*cur=head;
	temp=(node *)malloc(sizeof(node));
	printf("\nEnter the data....");
	scanf("%d",&temp->item);
	while(cur->next!=NULL)
	{
	cur=cur->next;
	}
	temp->next=cur->next;
	cur->next=temp;

	
}

void delBeg()
{
	node *temp=head;
	head=head->next;
	free(temp);
}

void delLast()
{
	node *temp,*cur=head;
	while(cur->next->next!=NULL)
	{
		cur=cur->next;
	}
	temp=cur->next;
	cur->next=NULL;
	free(temp);
}

int addAfter(int num)
{
	node *temp;
	temp = head;
	
	while(temp !=NULL)
	{
		if (temp->item==num)
		{
			node *p;
			p=(struct node*)malloc(sizeof(node));
			printf("enter data");
			scanf("%d", &(p->item));
			p->next=NULL;
			p->next=temp->next;
			temp->next=p;
		}
		else
			temp=temp->next;
	}
}

void display()
{
	node *cur=head;
	printf("\nHead->");
	while(cur!=NULL)
	{
		printf("\t%d",cur->item);
		cur=cur->next;
	}
	printf("<-NULL\n");
}

void prompt() {
	printf("\n1 INSERT a node at the END of linklist\n");
	printf("2 INSERT a node at the BEGINNING of linklist\n");
	printf("3 DELETE a node at the END of linklist\n");
	printf("4 DELETE a node from the BEGINNING of linklist\n");
	printf("5 INSERT a node in the MIDDLE of linklist\n");
	printf("6 DELET a node from the MIDDLE of linklist\n");
	printf("7 MODIFY any node in linklist\n");
	printf("8 EXIT\n");
}

int ask_num(){
	struct link *node;
    int num;
    printf("Enter a positive integer: ");
    scanf("%d", &num);
    return num;
    }
	
int linkedLists(){
	struct link *node;
	int choice;
	int num;
	do {
		prompt();
		scanf("%d", &choice);
	switch (choice) {
		case 1:
			addend();
			display();
			break;
		case 2:
			addfirst();
			display();
			break;
		case 3:
			delLast();
			display();
			break;
		case 4:
			delBeg();
			display();
		case 5:
			addAfter(num);
			display();
		case 8:
			break;
		}
	}
	while (choice != 8);
	return 0;
}

I'm also trying to get it to add a node after specific number, meaning that the program will search for that number then insert a node after it. This is what I'm trying to accomplish in my addAfter function. However, I keep getting segmentation faults in addition to nothing happening when I call that function.

Any ideas?
 
Z

Zeppelin

Member
Code: 
[B]#include <stdlib.h>
#include <memory.h>
#include <stdio.h>[/B]

struct link
{
	int item;
	struct link *next;
};
typedef struct link node;

node *head=NULL;

void addfirst()
{
	node *temp;
	temp=(node *)malloc(sizeof(node));
	printf("Enter the data....\t");
	scanf("%d",&temp->item);
	temp->next=head;
	head=temp;
}

void addend()
{
	node *temp,*cur=head;
	temp=(node *)malloc(sizeof(node));
	printf("\nEnter the data....");
	scanf("%d",&temp->item);
	while(cur->next!=NULL)
	{
	cur=cur->next;
	}
	temp->next=cur->next;
	cur->next=temp;

	
}

void delBeg()
{
	node *temp=head;
	head=head->next;
	free(temp);
}

void delLast()
{
	node *temp,*cur=head;
	while(cur->next->next!=NULL)
	{
		cur=cur->next;
	}
	temp=cur->next;
	cur->next=NULL;
	free(temp);
}

int addAfter(int num)
{
	node *temp;
	temp = head;
	
	while(temp !=NULL)
	{
		if (temp->item == num)
		{
			node *p;
[B]			p=(node*)malloc(sizeof(node));[/B]
			printf("enter data");
			scanf("%d", &(p->item));
[B]			// p->next=NULL;[/B]
			p->next=temp->next;
			temp->next=p;
[B]			return 0;[/B]
		}
		else
			temp=temp->next;
	}
}

void display()
{
	node *cur=head;
	printf("\nHead->");
	while(cur!=NULL)
	{
		printf("\t%d",cur->item);
		cur=cur->next;
	}
	printf("<-NULL\n");
}

void prompt() {
	printf("\n1 INSERT a node at the END of linklist\n");
	printf("2 INSERT a node at the BEGINNING of linklist\n");
	printf("3 DELETE a node at the END of linklist\n");
	printf("4 DELETE a node from the BEGINNING of linklist\n");
	printf("5 INSERT a node in the MIDDLE of linklist\n");
	printf("6 DELET a node from the MIDDLE of linklist\n");
	printf("7 MODIFY any node in linklist\n");
	printf("8 EXIT\n");
}

int ask_num(){
	struct link *node;
    int num;
    printf("Enter a positive integer: ");
    scanf("%d", &num);
    return num;
    }
	
int linkedLists(){
	struct link *node;
	int choice;
	int num;
	do {
		prompt();
		scanf("%d", &choice);
	switch (choice) {
		case 1:
			addend();
			display();
			break;
		case 2:
			addfirst();
			display();
			break;
		case 3:
			delLast();
			display();
			break;
		case 4:
			delBeg();
			display();
		case 5:
[B]			scanf("%d", &num);[/B]
			addAfter(num);
			display();
		case 8:
			break;
		}
	}
	while (choice != 8);
	return 0;
}

[B]int main(void) {
	linkedLists();
	return 0;
}[/B]

My additions in bold.
 
P

peppermints

Member
Zeppelin said:
Code: 
[B]#include <stdlib.h>
#include <memory.h>
#include <stdio.h>[/B]

struct link
{
	int item;
	struct link *next;
};
typedef struct link node;

node *head=NULL;

void addfirst()
{
	node *temp;
	temp=(node *)malloc(sizeof(node));
	printf("Enter the data....\t");
	scanf("%d",&temp->item);
	temp->next=head;
	head=temp;
}

void addend()
{
	node *temp,*cur=head;
	temp=(node *)malloc(sizeof(node));
	printf("\nEnter the data....");
	scanf("%d",&temp->item);
	while(cur->next!=NULL)
	{
	cur=cur->next;
	}
	temp->next=cur->next;
	cur->next=temp;

	
}

void delBeg()
{
	node *temp=head;
	head=head->next;
	free(temp);
}

void delLast()
{
	node *temp,*cur=head;
	while(cur->next->next!=NULL)
	{
		cur=cur->next;
	}
	temp=cur->next;
	cur->next=NULL;
	free(temp);
}

int addAfter(int num)
{
	node *temp;
	temp = head;
	
	while(temp !=NULL)
	{
		if (temp->item == num)
		{
			node *p;
[B]			p=(node*)malloc(sizeof(node));[/B]
			printf("enter data");
			scanf("%d", &(p->item));
[B]			// p->next=NULL;[/B]
			p->next=temp->next;
			temp->next=p;
[B]			return 0;[/B]
		}
		else
			temp=temp->next;
	}
}

void display()
{
	node *cur=head;
	printf("\nHead->");
	while(cur!=NULL)
	{
		printf("\t%d",cur->item);
		cur=cur->next;
	}
	printf("<-NULL\n");
}

void prompt() {
	printf("\n1 INSERT a node at the END of linklist\n");
	printf("2 INSERT a node at the BEGINNING of linklist\n");
	printf("3 DELETE a node at the END of linklist\n");
	printf("4 DELETE a node from the BEGINNING of linklist\n");
	printf("5 INSERT a node in the MIDDLE of linklist\n");
	printf("6 DELET a node from the MIDDLE of linklist\n");
	printf("7 MODIFY any node in linklist\n");
	printf("8 EXIT\n");
}

int ask_num(){
	struct link *node;
    int num;
    printf("Enter a positive integer: ");
    scanf("%d", &num);
    return num;
    }
	
int linkedLists(){
	struct link *node;
	int choice;
	int num;
	do {
		prompt();
		scanf("%d", &choice);
	switch (choice) {
		case 1:
			addend();
			display();
			break;
		case 2:
			addfirst();
			display();
			break;
		case 3:
			delLast();
			display();
			break;
		case 4:
			delBeg();
			display();
		case 5:
[B]			scanf("%d", &num);[/B]
			addAfter(num);
			display();
		case 8:
			break;
		}
	}
	while (choice != 8);
	return 0;
}

[B]int main(void) {
	linkedLists();
	return 0;
}[/B]

My additions in bold.
Click to expand...

Thanks, I already had stdio and stlib in, just forgot to copy and paste them on here. Any particular reason for using memory?
 
P

peppermints

Member
Okay, thanks, I've gotten it to work now with those changes.. I appreciate it. I'm sure I'll be back in this thread later if I have any other problems.
 
P

peppermints

Member
Okay now I'm a bit confused why this one isn't working.. it's following the same structure as adding to the middle, except instead of adding a node, I'm deleting one.

Code: 
int delAfter(int num)
{
	node *temp;
	temp = head;
	
	while(temp !=NULL)
	{
		if (temp->item==num)
		{
			node *p;
			p=(node*)malloc(sizeof(node));
			printf("enter data");
			scanf("%d", &(p->item));
			temp = head;
			free(head);
			head = temp;
			return 0;
		}
		else
			temp=temp->next;
	}
}
 
L

Lucis

Member
Run it through GDB? see what's wrong, debugging is part of programming.

There's no such thing as link list in C or link list in Java or link list in ASM, it's the same thing. Concept is a concept.
 
Z

Zeppelin

Member
peppermints said:
Thanks, I already had stdio and stlib in, just forgot to copy and paste them on here. Any particular reason for using memory?
Click to expand...

Na, I just threw it in there when I was trying to get it to compile.

peppermints said:
Okay now I'm a bit confused why this one isn't working.. it's following the same structure as adding to the middle, except instead of adding a node, I'm deleting one.

Code: 
int delAfter(int num)
{
	node *temp;
	temp = head;
	
	while(temp !=NULL)
	{
		if (temp->item==num)
		{
			node *p;
			p=(node*)malloc(sizeof(node));
			printf("enter data");
			scanf("%d", &(p->item));
			temp = head;
			free(head);
			head = temp;
			return 0;
		}
		else
			temp=temp->next;
	}
}
Click to expand...

Think about what you're trying to accomplish. If you're gonna delete the element at position n in the list you need to fetch the element at position n + 1 and make element n - 1 point to that instead of element n.

Drawing a diagram like this one might help: http://www.ele.uri.edu/Courses/ele408/LinkList.gif
 
P

peppermints

Member
I don't get any compile errors, it compiles and runs. The problem is now that when I call delAfter, it doesn't do anything and I'm not sure why.
 
S

squidyj

Member
peppermints said:
Okay now I'm a bit confused why this one isn't working.. it's following the same structure as adding to the middle, except instead of adding a node, I'm deleting one.

Code: 
int delAfter(int num)
{
	node *temp;
        node *prev;
	temp = head;
        prev = temp;
	
	while(temp !=NULL)
	{
		if (temp->item==num)
		{
			prev->next = temp->next;
			free(temp);
			return 0;
		}
		else
                {
                        prev=temp;
			temp=temp->next;
	}
}
Click to expand...

Well okay first of all for clarity's sake and for the sake of the user I'd scrub all that data entry stuff from your function.
What you're doing is after you set your temp node to reference the same address as the head and you find your place in the list you throw away the address referenced to by temp with the line temp = head; at which point nothing you do is going to do anything useful.
Looks like it's singly linked so all you really want to do is store the previous node and your current node and then set previousnode->next to currentnode->next and then blow out your current node and you're done.
 
B

bluemax

Banned
peppermints said:
I don't get any compile errors, it compiles and runs. The problem is now that when I call delAfter, it doesn't do anything and I'm not sure why.
Click to expand...

I'm on my phone so I can't see your code but I'm guessing you're doing something in the wrong order or not updating a next pointer somewhere.

I've lost track of how many times I've done linked lists in interviews.
 
T

Tomat

Wanna hear a good joke? Waste your time helping me! LOL!
Tagging this for later, I feel your pain peppermints... I have a C++ program due on Wednesday (that I haven't even started of course). Need to use linked lists and sort them alphabetically.
 
Z

Zeppelin

Member
peppermints said:
I don't get any compile errors, it compiles and runs. The problem is now that when I call delAfter, it doesn't do anything and I'm not sure why.
Click to expand...

Thing is your code doesn't make sense. Why are you doing free(head)? Anyway, I gotta go to school. Hopefully someone else can help you out.
 
P

peppermints

Member
Zeppelin said:
Thing is your code doesn't make sense. Why are you doing free(head)? Anyway, I gotta go to school. Hopefully someone else can help you out.
Click to expand...

Haha, I know, now that I'm staring at it, it really doesn't make sense. Thanks for your help, and everyone elses. Hopefully I'll get this sorted out soon.
 
S

squidyj

Member
peppermints said:
Haha, I know, now that I'm staring at it, it really doesn't make sense. Thanks for your help, and everyone elses. Hopefully I'll get this sorted out soon.
Click to expand...

Made some adjustments to your code, look it over, I haven't done this shit in years.

Code: 
int delAfter(int num)
{
	node *temp;
        node *prev;
	temp = head;
        prev = NULL;  	

	while(temp !=NULL)
	{
		if (temp->item==num)
		{
                        if(prev != NULL)
                        {
			       prev->next = temp->next;
			       free(temp);	       
                        }
                        else
                        {
                               head = temp->next;
                               free(head);
                        }
                        return 0;
		}
		else
                {
                        prev=temp;
			temp=temp->next;
                }
	}
}

Almost forgot the case where the first node was the sought after one.
 
D

Dr Zhivago

Member
I'd strongly suggest giving your global pointer a better name than just 'head'.
g_Head or g_ListHeadPointer or something.
 
S

squidyj

Member
Dr Zhivago said:
I'd strongly suggest giving your global pointer a better name than just 'head'.
g_Head or g_ListHeadPointer or something.
Click to expand...

also, by not doing it as a class and returning head via method you rob yourself of the opportunity to write a bunch of lines that say gethead
 
Status
Not open for further replies.

Similar threads

  • Locked
C programing question and Yes its my final project
9
950
Ophiuchus replied
  • Locked
Why am I getting this weird Bus error? C programming
2
780
Shompola replied
Holiday '08 List Of Limited Editions, Special Editions, & Preorder Goodies Worldwide
2
60
17K
Rlan replied
Roguelikes and Jade
2 3
103
19K
slayn replied
Twin Galaxies 2005 bounties...earn cash for gaming records
1
3K
Bog replied
Top Bottom