Thread: Singly Linked List

Here's a program which is found in my text boob of C. I don't know what and how it does the work. When I ran it, it had errors which I rectified somehow.

Code:

#include <stdio.h>
#include <conio.h>

#include <alloc.h>


#define NewNode (Node *) malloc(sizeof(Node))

typedef struct node {

	int item;
	struct node *next;

}Node;

Node * Create(Node *);
void Display(Node *);
int Count(Node *);
Node * Insert(Node *);
Node * Delete(Node *);
void Search(Node *);



void main() {

	Node *start = NULL;
	int ch, cnt;
	clrscr();
	start = Create(start);
	Display(start);

	do {

		printf("\n Singly Linked List Operations \n");

		printf(" 1->  Count\n");
		printf(" 2->  Display\n");
		printf(" 3->  Insert\n");
		printf(" 4->  Delete\n");
		printf(" 5->  Search\n");

		printf("\n Enter a Choice: ");
		scanf("%d", &ch);


		switch(ch) {

			case 1:

				printf("\n No. of Nodes = %d\n", Count(start));
				break;

			case 2:

				Display(start);
				break;

			case 3:

				start = Insert(start);
				break;

			case 4:

				start = Delete(start);
				break;

			case 5:

				Search(start);
				break;

			default:

				printf("\n Invalid Selection\n");

		}

	}while(ch !=0);
}

Node * Create(Node *s) {

	Node *tmp = NULL, *t1 = NULL;
	int num;
	t1 =s;

	do {

		printf("\n Enter the element: ");
		scanf("%d", &num);

		if(num != -99) {

			tmp = NewNode;
			tmp->item = num;
			tmp->next = NULL;

			if(s == NULL)
				s = t1 = tmp;
			else {

				t1->next = tmp;
				t1 = t1->next;
			}

		}

		else {

			printf("\n Linked List Created Successfully\n");
		}
	}while(num != -99);
	return(s);
}

void Display(Node *s) {

	if(s == NULL)
		printf("\n Empty Linked List\n");
	else {
		while(s != NULL) {

			printf("%d", s->item);
			s = s->next;
		}
		printf("\n ");
	}
}

int Count(Node *s) {

	int total = 0;

	while(s != NULL) {

		total++;
		s = s->next;
	}
	return(total);

}

Node * Insert(Node *s) {

	Node *t1 = NULL, *tmp = NewNode;
	int pos;

	printf("\n Enter the position to be inserted \n");
	scanf("%d", &pos);

	if(pos > 0 && pos <= Count(s) + 1) {
		printf("\n Enter the element to inserted\n");
		scanf("%d", &tmp->item);

		if(pos == 1) {
			tmp->next = s;
			s = tmp;
		}
		else {
			t1 = s;
			while(pos > 2) {
				t1 = t1->next;
				pos--;
			}
			tmp->next = t1->next;
			t1->next = tmp;
		}
	}
	else {
		printf("\n Invalid Position\n");
	}

	return(s);
}

Node * Delete(Node *s) {

	Node *t1 = s, *tmp = NULL;
	int pos;
	printf("\n Enter the position to be deleted\n");
	scanf("%d", &pos);

	if(pos > 0 && pos <= Count(s)) {

		if(pos == 1) {
			s = s->next;
			free(t1);
		}
		else {
			while(pos > 2) {
				t1 = t1->next;
				pos--;
			}

		tmp = t1->next;
		t1->next = tmp->next;
		free(tmp);

		}
	}
	else {
		printf("\n Invalid Position\n");
	}
	return(s);
}

void Search(Node *s) {

	int ele;
	int flag = 0;

	printf("\n Enter the element to be searched: ");
	scanf("%d", &ele);

	if(s !=NULL) {

		while(s != NULL) {
			if(s->item == ele) {
				printf("\n%d is present\n", ele);
				flag = 1;
			}
			s = s->next;
		}

		if(flag == 0) {
			printf("\nElement Not Found\n");
		}
	else {
		printf("\nList is Empty. Key Element Can't be searched.\n");
	}
	}
}

Here's the first run of the program:

Code:

C:\node


Enter the element: -99

Linked List Created Successfully

Empty Linked List

Singly Linked List Operations
1->  Count
2->  Display
3->  Insert
4->  Delete
5->  Search

Enter a Choice: 3

 Enter the position to be inserted
1

 Enter the element to inserted
100

 Singly Linked List Operations
 1->  Count
 2->  Display
 3->  Insert
 4->  Delete
 5->  Search

 Enter a Choice:

So, any explanation? My text book doesn't say anything about it.

No, Laser Light, my text book doesn't explain the code. It has simply stated what type of linked list are there and what they do. But it says nothing about how they work and are used.

Originally Posted by laserlight

Does your text book not explain the code?

Well, a node is something really simple. It contains an item and a pointer. The item is the value it holds. the pointer points to the next node, so you can have a row of nodes, and each one can be accessed by the previous one. (Except the first one) So, if you have 1 node, you can rush through all of them. But look here, I would start small: struct definition, print the item, get the next node, bounds (last node might be a NULL pointer) etc. Not as fullblown as in your book:

Linked Lists

Originally Posted by devarishi

So, any explanation? My text book doesn't say anything about it.

Let's assume that you understand how pointers work. you could just take a look at this link, it's not an explanation but a graphical presentation on how link list works. This helped me a lot