Abhigyan’s Notes
Abhigyan’s Notes
(DS4) Links & Chains
⛓️

(DS4) Links & Chains

Linked ListsTypes of Linked ListsSingly Linked ListsTransforming Linked ListsAs A StackAs A QueueAs A Double-Ended QueueOrdered Linked ListsCircular Linked ListsDoubly Linked ListsQuestions
 

Linked Lists

It is a structure that consists of many nodes, utilizing C’s built-in malloc() function for dynamic memory allocation.
notion image
Advantages:
  1. Stored in non-contiguous memory allocations (dynamic size).
  1. Lesser number of operations for insertion/deletion.
Disadvantages:
  1. Needs extra space because each node stores the address of other nodes.
  1. Accessing a particular node may take more time.

Types of Linked Lists

  1. Singly linked lists.
  1. Circular linked lists.
  1. Doubly linked lists.
  1. Circular doubly linked lists. (Not covering this in this module.)

Singly Linked Lists

#include <stdio.h>
#include <stdlib.h>
#include <stddef.h>

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

Node getNode();
Node insertFront(int item, Node head);
Node insertRear(int item, Node head);
Node deleteFront(Node head);
Node deleteRear(Node head);
void display(Node head);

void main()
{
	Node head = NULL;
	int choice, item;

	for (;;)
	{
		printf("\n--- LINKED LIST OPERATIONS ---");
		printf("\n1. Insert Front");
		printf("\n2. Insert Rear");
		printf("\n3. Delete Front");
		printf("\n4. Delete Rear");
		printf("\n5. Display");
		printf("\n6. Exit.");

		printf("\n\nEnter your choice: ");
		scanf("%d", &choice);

		switch (choice)
		{
		case 1:
			printf("\n\nEnter the item to be added: ");
			scanf("%d", &item);
			head = insertFront(item, head);
			display(head);
			break;
		case 2:
			printf("\n\nEnter the item to be added: ");
			scanf("%d", &item);
			head = insertRear(item, head);
			display(head);
			break;
		case 3:
			head = deleteFront(head);
			display(head);
			break;
		case 4:
			head = deleteRear(head);
			display(head);
			break;
		case 5:
			display(head);
			break;
		case 6:
			exit(0);
		default:
			printf("\n\nERROR | Invalid input.");
			break;
		}
	}
}

Node getNode()
{
	Node temp = (Node)malloc(sizeof(Node));
	if (temp == NULL)
	{
		printf("\nERROR | Out of memory.\n");
	}
	return temp;
}

Node insertFront(int item, Node head)
{
	Node temp = getNode();
	temp->item = item;
	temp->next = head;
	return temp;
}

Node insertRear(int item, Node head)
{
	Node temp, list;
	temp = getNode();
	temp->item = item;
	temp->next = NULL;
	if (head == NULL)
	{
		// if list is empty then create it.
		return temp;
	}
	list = head;
	while (list != NULL)
	{
		list = list->next;
	}
	list->next = temp;
	return head;
}

Node deleteFront(Node head)
{
	Node temp;
	if (head == NULL)
	{
		printf("\nERROR | List is empty.\n");
		return head;
	}
	temp = head;
	head = head->next;
	free(temp);
	return head;
}

Node deleteRear(Node head)
{
	Node rear, list;
	if (head == NULL)
	{
		printf("\nERROR | List is empty.\n");
		return head;
	}
	// if there is only one node, delete and set to NULL.
	if (head->next == NULL)
	{
		free(head);
		return head;
	}

	rear = NULL;
	list = head;
	while (list->next != NULL)
	{
		rear = list;
		list = list->next;
	}
	free(list);
	rear->next = NULL;

	return head;
}

void display(Node head)
{
	Node temp;
	printf("\nValues: \n");
	for (temp = head; temp != NULL; temp = temp->next)
	{
		printf("| %d | %p -> ", temp->item, temp->next);
	}
	printf("\n\nHead Node Address: %p \n", head);
}

Transforming Linked Lists

As A Stack

It can be implemented by providing the above insertFront() and deleteFront() functions.

As A Queue

It can be implemented by providing the above insertRear() and deleteFront() functions.

As A Double-Ended Queue

It can be implemented by using all four of the insertFront(), insertRear(), deleteFront() and deleteRear() functions.

Ordered Linked Lists

This requires traversing till the smaller element is passed, inserting the new element, and then attaching it to the rest of the list.
Node insert(int item, Node head)
{
	Node temp, list, prev;
	temp = getNode();
	temp->item = item;
	temp->next = NULL;

	if (head == NULL)
		return temp;

	// if item is less than first node, return as new node.
	if (item < head->item)
	{
		temp->next = head;
		return temp;
	}

	// else traverse till item is greater than the node items.
	prev = NULL;
	list = head;
	while (list != NULL && item > list->item)
	{
		prev = list;
		list = list->next;
	}

	// set previous node to new, new to current.
	prev->next = temp;
	temp->next = list;
	return head;
}
A similar approach would be required to merge two ordered lists, but the functions will take in the pointers to the lists rather than the items.
Header Nodes are dummy nodes at the head of the list to act as an info field; they don’t represent any item in the list, but usually specify the number of nodes in the list.

Circular Linked Lists

Usually, we can reach all the nodes after a certain node, but not the ones before (as rear points to NULL). But a circular linked list is implemented by keeping track of the rear node, which then points to the head.
insert() and delete() functions here return the rear node, unlike singly linked lists.

Doubly Linked Lists

This includes the insertPos() and deletePos() methods.
#include <stdio.h>
#include <stdlib.h>
#include <stddef.h>

typedef struct node
{
	struct node *prev;
	int item;
	struct node *next;
} *Node;

Node getNode();
Node insertFront(int item, Node head);
Node insertPos(int item, int index, Node head);
Node insertRear(int item, Node head);
Node deleteFront(Node head);
Node deletePos(int index, Node head);
Node deleteRear(Node head);
void display(Node head);

void main()
{
	Node head = NULL;
	int choice, item, index;

	for (;;)
	{
		printf("\n--- LINKED LIST OPERATIONS ---");
		printf("\n1. Insert Front");
		printf("\n2. Insert At Position");
		printf("\n3. Insert Rear");
		printf("\n4. Delete Front");
		printf("\n5. Delete At Position");
		printf("\n6. Delete Rear");
		printf("\n7. Display");
		printf("\n8. Exit.");

		printf("\n\nEnter your choice: ");
		scanf("%d", &choice);

		switch (choice)
		{
		case 1:
			printf("\n\nEnter the item to be added: ");
			scanf("%d", &item);
			head = insertFront(item, head);
			display(head);
			break;
		case 2:
			printf("\n\nEnter the item and index to be added: ");
			scanf("%d %d", &item, &index);
			head = insertPos(item, index, head);
			display(head);
			break;
		case 3:
			printf("\n\nEnter the item to be added: ");
			scanf("%d", &item);
			head = insertRear(item, head);
			display(head);
			break;
		case 4:
			head = deleteFront(head);
			display(head);
			break;
		case 5:
			printf("\n\nEnter the index to be deleted: ");
			scanf("%d", &index);
			head = deletePos(index, head);
			display(head);
			break;
		case 6:
			head = deleteRear(head);
			display(head);
			break;
		case 7:
			display(head);
			break;
		case 8:
			exit(0);
		default:
			printf("\n\nERROR | Invalid input.");
			break;
		}
	}
}

Node getNode()
{
	Node temp = (Node)malloc(sizeof(Node));
	if (temp == NULL)
	{
		printf("\nERROR | Out of memory.\n");
		exit(0);
	}
	return temp;
}

Node insertFront(int item, Node head)
{
	Node temp = getNode();
	if (head != NULL)
		head->prev = temp;
	temp->prev = NULL;
	temp->item = item;
	temp->next = head;
	return temp;
}

Node insertPos(int item, int index, Node head)
{
	Node temp, list;
	int count;

	if (head == NULL)
	{
		printf("\nERROR | List is empty.\n");
		return head;
	}

	temp = getNode();
	list = head;
	for (count = -1; count < index; count++)
	{
		if (list == NULL)
		{
			printf("\nERROR | Position doesn't exist.\n");
			return head;
		}
		list = list->next;
	}
	temp->prev = list->prev;
	list->prev = temp;
	temp->item = item;
	temp->next = list;
	temp->prev->next = temp;
	return head;
}

Node insertRear(int item, Node head)
{
	Node temp, list;
	temp = getNode();
	temp->prev = NULL;
	temp->item = item;
	temp->next = NULL;
	if (head == NULL)
	{
		// if list is empty then create it.
		return temp;
	}
	list = head;
	while (list != NULL)
	{
		list = list->next;
	}
	temp->prev = list;
	list->next = temp;
	return head;
}

Node deleteFront(Node head)
{
	Node temp;
	if (head == NULL)
	{
		printf("\nERROR | List is empty.\n");
		return head;
	}
	temp = head;
	head = head->next;
	head->prev = NULL;
	free(temp);
	return head;
}

Node deletePos(int index, Node head)
{
	Node temp, list;
	int count;

	if (head == NULL)
	{
		printf("\nERROR | List is empty.\n");
		return head;
	}

	temp = getNode();
	list = head;
	for (count = -1; count < index; count++)
	{
		if (list == NULL)
		{
			printf("\nERROR | Position doesn't exist.\n");
			return head;
		}
		list = list->next;
	}
	temp = list->next;
	temp->next->prev = list;
	list->next = temp->next;
	free(temp);
	return head;
}

Node deleteRear(Node head)
{
	Node rear, list;
	if (head == NULL)
	{
		printf("\nERROR | List is empty.\n");
		return head;
	}
	// if there is only one node, delete and set to NULL.
	if (head->next == NULL)
	{
		free(head);
		return head;
	}

	rear = NULL;
	list = head;
	while (list->next != NULL)
	{
		rear = list;
		list = list->next;
	}
	free(list);
	rear->next = NULL;

	return head;
}

void display(Node head)
{
	Node temp;
	printf("\nValues: \n");
	for (temp = head; temp != NULL; temp = temp->next)
	{
		printf("%p | %d | %p <-> ", temp->prev, temp->item, temp->next);
	}
	printf("\n\nHead Node Address: %p \n", head);
}

Questions

Q. WAP to sort a linked list.
Q. WAP to search for an item in a linked list.
  • Start from the head and traverse.
  • If the item is found, display it.
  • If it’s not found (EOL), then display an error.
Q. WAP to concatenate two linked lists.
  • If the first list is empty, return the first node of the second list (vice versa).
  • If both are non-empty, then traverse till the end of the first list and link the rear to the first node of the second list.
  • Return the first node of the first list.
Q. WAP to reverse a list without creating new nodes.
Node reverse(Node head)
{
	Node temp, cursor;
	while (head != NULL)
	{
		temp = head;
		head = head->next;
		temp->next = cursor;
		cursor = temp;
	}
	return cursor;
}
Q. WAP to add two given polynomials.
// https://www.prepbytes.com/blog/linked-list/adding-two-polynomials-using-linked-list/
#include <stdio.h>
#include <stdlib.h>

typedef struct Node
{
	int coef;
	int exp;
	struct Node *next;
} Node;

void insert(Node **poly, int coef, int exp)
{
	Node *temp = (Node *)malloc(sizeof(Node));
	temp->coef = coef;
	temp->exp = exp;
	temp->next = NULL;

	if (*poly == NULL || (*poly)->exp < exp)
	{
		temp->next = *poly;
		*poly = temp;
	}
	else
	{
		Node *current = *poly;
		while (current->next != NULL && current->next->exp >= exp)
		{
			current = current->next;
		}
		temp->next = current->next;
		current->next = temp;
	}
}

void print(Node *poly)
{
	if (poly == NULL)
	{
		printf("0\n");
		return;
	}

	Node *current = poly;
	while (current != NULL)
	{
		printf("%dx^%d", current->coef, current->exp);
		if (current->next != NULL)
		{
			printf(" + ");
		}
		current = current->next;
	}
	printf("\n");
}

Node *add(Node *poly1, Node *poly2)
{
	if (poly1 == NULL)
	{
		return poly2;
	}
	if (poly2 == NULL)
	{
		return poly1;
	}

	Node *result = NULL;

	if (poly1->exp == poly2->exp)
	{
		result = (Node *)malloc(sizeof(Node));
		result->coef = poly1->coef + poly2->coef;
		result->exp = poly1->exp;
		result->next = add(poly1->next, poly2->next);
	}
	else if (poly1->exp > poly2->exp)
	{
		result = (Node *)malloc(sizeof(Node));
		result->coef = poly1->coef;
		result->exp = poly1->exp;
		result->next = add(poly1->next, poly2);
	}
	else
	{
		result = (Node *)malloc(sizeof(Node));
		result->coef = poly2->coef;
		result->exp = poly2->exp;
		result->next = add(poly1, poly2->next);
	}
	return result;
}

int main()
{
	Node *poly1 = NULL;
	Node *poly2 = NULL;

	insert(&poly1, 1, 2);
	insert(&poly1, 3, 1);
	insert(&poly1, 2, 0);
	printf("Poly 1: ");
	print(poly1);

	insert(&poly2, 4, 3);
	insert(&poly2, 2, 1);
	printf("Poly 2: ");
	print(poly2);

	Node *sum = add(poly1, poly2);
	printf("Sum: ");
	print(sum);

	return 0;
}