Linked-Lists in C

Linked-lists utilize nodes of data. A node consists of two parts: a data part and a link part. The data part contains the data actually stored by the node. The link part consists of one or more pointers to other nodes. These pointers contain the addresses in memory of other nodes.

A linked list consists of a node that is the head or first node, that links to another node, that in turn links to another node, until finally the last node has a link set to NULL.

typedef struct node {
	char data; 
	struct node *link;
} NODE;

Nodes are created dynamically as needed during run time. In C, we do this using the malloc() function contained in the <stdlib.h> library. Linked-list nodes are created by dynamically allocating chunks of memory large enough to store the node. The nodes must be set to either point to another node, or else by NULL if it is at the end of the list.

void displayList(NODE *ptr);

int main()
{
	NODE *nOne, *nTwo, *nThree, *nFour;

	nOne = (NODE *)malloc(sizeof(NODE));
	nTwo = (NODE *)malloc(sizeof(NODE));
	nThree = (NODE *)malloc(sizeof(NODE));
	nFour = (NODE *)malloc(sizeof(NODE));

	nOne->data = 't';
	nOne->link = nTwo;

	nTwo->data = 'r';
	nTwo->link = nThree;

	nThree->data = 'e';
	nThree->link = nFour;

	nFour->data = 'e';
	nFour->link = NULL;


	displayList(nOne);

    return 0;
}

void displayList(NODE *ptr) {
	while (ptr != NULL) {
		printf("%c\t", ptr->data);
		ptr = ptr->link;
	}
	printf("\n\n");
}

As linked-lists are created dynamically, just adding a node isn’t just adding a node. Whenever we add a node, we have to consider several possible cases according to where in the list the node is being added and whether or not the list is empty.

The addNode() function uses a while loop to find the last node in the list before  allocating a new node and attaching it to the last node.

Adding a new node to the beginning of the list is simpler.

typedef struct node {
	int data;
	struct node *link;
} NODE;

void showList(NODE *ptr);
void addNode(NODE **ptr, int data);
void prependNode(NODE **ptr, int data);

int main() {
	
	const int buffer_size = 64;

	char buffer[buffer_size];
	NODE *n = NULL;
	int i = 0;
	int data;
	
	while (i++ < 5) { 		printf("Please enter a number: "); 		fgets(buffer, buffer_size, stdin); 		addNode(&n, atoi(buffer)); 	} 	 	printf("The link list is: \n"); 	showList(n); 	 	return 0; } void showList(NODE *ptr) { 	while (ptr != NULL) { 		printf("%d\t", ptr->data);
		ptr = ptr->link;
	}
}

void prependNode(NODE **ptr, int data) {
	NODE *nOne = (NODE *)malloc(sizeof(NODE));
	if (nOne != NULL) {
		nOne->data = data;
		nOne->link = *ptr;
		*ptr = nOne;
	}
}

void addNode(NODE **ptr, int data) {
	NODE *pOne, *pTwo;

	pOne = *ptr;
	if (pOne == NULL) {
		//empty list
		pOne = (NODE *)malloc(sizeof(NODE));
		if (pOne != NULL) {
			pOne->data = data;
			pOne->link = NULL;
			*ptr = pOne;
		}
	}
	else {
		while (pOne->link != NULL) {
			pOne = pOne->link;
		}
		pTwo = (NODE *)malloc(sizeof(NODE));
		if (pTwo != NULL) {
			pTwo->data = data;
			pTwo->link = NULL;
			pOne->link = pTwo;
		}
	}
}

Sometimes we may need to delete a node from a linked list. We can delete a node from the beginning of the linked list, from the end of the list, or from somewhere in the middle. We use the free() function to return the memory back to the heap.

void deleteFromHead(NODE **ptr) {
	NODE *head;
	head = *ptr;
	if (head != NULL) {
		head = head->link;
		free(*ptr);
	}
	*ptr = head;
}

To delete the node from the tail of a linked list we search to find the last node in the list.

typedef struct node {
	double data;
	struct node *link;
} NODE;

void viewList(NODE *ptr);
void deleteTail(NODE **ptr);

int main() {
	
	NODE *nOne, *nTwo, *nThree, *nFour;

	nOne = (NODE *)malloc(sizeof(NODE));
	nTwo = (NODE *)malloc(sizeof(NODE));
	nThree = (NODE *)malloc(sizeof(NODE));
	nFour = (NODE *)malloc(sizeof(NODE));

	nOne->data = 2.718;
	nOne->link = nTwo;

	nTwo->data = 1.491625;
	nTwo->link = nThree;

	nThree->data = 169.254;
	nThree->link = nFour;

	nFour->data = 0.57721;
	nFour->link = NULL;

	viewList(nOne);

	deleteTail(&nOne);

	viewList(nOne);

	return 0;
}

void viewList(NODE *ptr) {
	printf("\n");
	while (ptr != NULL) {
		printf("%f\t", ptr->data);
		ptr = ptr->link;
	}
	printf("\n");
}

void deleteTail(NODE **ptr) {
	NODE *nOne, *nTwo;

	nOne = *ptr;
	if (nOne != NULL)
	{
		if (nOne->link == NULL) {
			free(*ptr);
			*ptr = NULL;
		}
		else {
			nTwo = nOne;
			while (nOne->link != NULL) {
				nTwo = nOne;
				nOne = nOne->link;
			}
			nTwo->link = NULL;
			free(nOne);
		}
	}
}

 

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s