Lists

A list is a data structure that can hold an ordered collection of items. Lists are commonly used in programming to organize data in a linear fashion. They allow for dynamic sizing and provide various operations for inserting, deleting, and accessing elements. Lists can be implemented in different ways, with linked lists being a popular choice.

4.1 List and ADT

What is a List?

A list is a linear data structure that stores a collection of elements in a specific order. It can contain duplicates and is typically dynamic in size, meaning it can grow or shrink as needed. Lists are versatile and can be implemented in various ways, such as:

Array-based Lists:
- Utilizes a contiguous block of memory.
- Allows indexed access to elements.
- Size is usually fixed, but dynamic arrays can resize.
Linked Lists:
- Composed of nodes where each node contains data and a reference to the next node.
- Supports dynamic sizing and efficient insertions/deletions.

Characteristics of Lists

Ordered Collection: Elements have a specific order and can be accessed sequentially.
Dynamic Size: The size of the list can change during execution.
Homogeneous/Non-Homogeneous: Lists can contain elements of the same type or different types, depending on implementation.

What is an Abstract Data Type (ADT)?

An Abstract Data Type (ADT) is a theoretical concept that defines a data type purely in terms of its behavior (operations and their properties) rather than its implementation. An ADT specifies:

What operations can be performed on the data type.
The behavior of these operations (e.g., expected input and output).
No specific implementation details are provided, allowing flexibility in how the data type is realized.

Lists as an ADT

When we consider lists as an ADT, we focus on the operations that can be performed on a list without worrying about how these operations are implemented. Here are some common operations associated with the List ADT:

Creation: Initialize a new list.
Insertion:
- At the beginning
- At the end
- At a specific position
Deletion:
- Remove an element by value
- Remove an element at a specific position
Traversal: Access each element in the list sequentially.
Searching: Find the presence or location of a specific element.
Modification: Change the value of an element at a specified position.
Size: Determine the number of elements in the list.
Clear: Remove all elements from the list.

Advantages of Using Lists as ADTs

Abstraction: Users interact with the list without needing to understand its implementation.
Flexibility: Different implementations (e.g., array-based, linked) can be swapped without affecting the code that uses the list.
Reusability: ADTs can be reused across different programs or modules.

Example of List ADT Operations

Here’s a pseudo-code representation of the List ADT:

ListADT {
// Creates an empty list
createList() -> List

// Inserts an element at a specified position
insert(list: List, element: Element, position: Integer)

// Deletes an element by value
delete(list: List, element: Element)

// Returns the size of the list
size(list: List) -> Integer

// Traverses the list and applies a function to each element
traverse(list: List, function: Function)

// Searches for an element in the list
search(list: List, element: Element) -> Boolean

// Clears the list
clear(list: List)
}

4.2 Array Implementation of Lists

The array implementation of lists is one of the simplest and most common ways to represent a list data structure. In this implementation, a list is backed by an array, allowing for efficient access and modification of elements. Below, we’ll discuss the characteristics, operations, advantages, and limitations of array implementations of lists.

Characteristics of Array Implementation

Fixed Size:
- The size of the array must be defined at the time of creation. This can lead to waste of space if the array is not fully utilized or require resizing if the list exceeds its capacity.
Indexed Access:
- Elements can be accessed directly using their indices, which makes access operations efficient (O(1) time complexity).
Contiguous Memory Allocation:
- All elements are stored in contiguous memory locations, which can improve cache performance.

Basic Operations on Array-Backed Lists

Here are the common operations you can perform on an array implementation of lists, along with their typical time complexities:

Creation:
- Initialize an array of a specified size.
Insertion:
- At the beginning: Shift all elements to the right and insert the new element at index 0.
  - Time Complexity: O(n)
- At the end: Add the new element at the next available index.
  - Time Complexity: O(1) if space is available; O(n) if resizing is needed.
- At a specific position: Shift elements after that position and insert the new element.
  - Time Complexity: O(n)
Deletion:
- By value: Search for the element, remove it, and shift subsequent elements left.
  - Time Complexity: O(n)
- At a specific position: Remove the element and shift subsequent elements left.
  - Time Complexity: O(n)
Traversal:
- Iterate through each element in the array.
  - Time Complexity: O(n)
Searching:
- Perform a linear search for an element.
  - Time Complexity: O(n)
Modification:
- Update the value at a specific index.
  - Time Complexity: O(1)
Size:
- Keep track of the number of elements.
  - Time Complexity: O(1)
Clear:
- Reset the size and optionally set all elements to a default value.
  - Time Complexity: O(n)

Example of Array Implementation in C

Here’s a simple implementation of an array-based list in C that supports basic operations:

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

#define MAX_SIZE 100 // Maximum size of the list

typedef struct {
int data[MAX_SIZE];
int size; // Current number of elements in the list
} ArrayList;

// Function to initialize the list
void initList(ArrayList* list) {
list->size = 0;
}

// Function to insert an element at the end
void insertEnd(ArrayList* list, int value) {
if (list->size < MAX_SIZE) {
list->data[list->size++] = value;
} else {
printf(“List is full. Cannot insert %d\n”, value);
}
}

// Function to insert an element at a specific position
void insertAt(ArrayList* list, int value, int position) {
if (position < 0 || position > list->size) {
printf(“Invalid position %d\n”, position);
return;
}
if (list->size < MAX_SIZE) {
for (int i = list->size; i > position; i–) {
list->data[i] = list->data[i – 1]; // Shift elements to the right
}
list->data[position] = value; // Insert the new element
list->size++;
} else {
printf(“List is full. Cannot insert %d\n”, value);
}
}

// Function to delete an element by value
void deleteByValue(ArrayList* list, int value) {
for (int i = 0; i < list->size; i++) {
if (list->data[i] == value) {
for (int j = i; j < list->size – 1; j++) {
list->data[j] = list->data[j + 1]; // Shift elements to the left
}
list->size–; // Reduce size
printf(“%d deleted from the list\n”, value);
return;
}
}
printf(“%d not found in the list\n”, value);
}

// Function to traverse the list
void traverseList(ArrayList* list) {
printf(“Array List: “);
for (int i = 0; i < list->size; i++) {
printf(“%d “, list->data[i]);
}
printf(“\n”);
}

// Function to search for an element
int searchList(ArrayList* list, int value) {
for (int i = 0; i < list->size; i++) {
if (list->data[i] == value) {
return i; // Return index of the element
}
}
return -1; // Not found
}

// Main function to demonstrate array list operations
int main() {
ArrayList list;
initList(&list);

// Inserting elements
insertEnd(&list, 10);
insertEnd(&list, 20);
insertEnd(&list, 30);
insertAt(&list, 15, 1); // Insert 15 at position 1

// Traversing the list
traverseList(&list);

// Searching for a value
int searchValue = 20;
int index = searchList(&list, searchValue);
if (index != -1) {
printf(“%d found at index %d\n”, searchValue, index);
} else {
printf(“%d not found in the list\n”, searchValue);
}

// Deleting a value
deleteByValue(&list, 15);
traverseList(&list);

// Clean up and exit
return 0;
}

Explanation of the Code

ArrayList Structure: Contains an array for data and an integer to track the current size of the list.
Initialization: The initList function initializes the list by setting the size to zero.
Insertion Functions:
- insertEnd: Adds a new element at the end if there is space.
- insertAt: Adds an element at a specified position, shifting existing elements if needed.
Deletion Function:
- deleteByValue: Searches for a specified value and removes it from the list, shifting remaining elements left.
Traversal Function:
- traverseList: Prints all elements in the list.
Search Function:
- searchList: Checks if a specific value exists in the list and returns its index.
Main Function: Demonstrates the various operations of the array list.

How to Compile and Run

Copy the complete code into a .c file (e.g., array_list.c).
Open a terminal and navigate to the directory containing the file.
Compile the program using:

gcc array_list.c -o array_list
Run the program with:

./array_list

This implementation will create a simple array-based list, allowing you to perform various operations and see the output for each operation.

4.3 Linked List

A linked list is a dynamic data structure that consists of a sequence of elements called nodes, where each node contains two components: data and a reference (or pointer) to the next node in the sequence. This structure allows for efficient insertions and deletions, as nodes can be added or removed without reallocating or reorganizing the entire list.

Characteristics of Linked Lists

Dynamic Size:
- Unlike arrays, linked lists can grow and shrink in size dynamically, allowing for more efficient memory utilization.
Non-contiguous Memory Allocation:
- Nodes are scattered throughout memory, which can lead to increased overhead in terms of memory usage for pointers.
Sequential Access:
- Unlike arrays, which allow random access to elements, linked lists require traversal from the head node to access elements sequentially.
Types of Linked Lists:
- Singly Linked List: Each node points to the next node, allowing traversal in one direction.
- Doubly Linked List: Each node contains pointers to both the next and previous nodes, allowing traversal in both directions.
- Circular Linked List: The last node points back to the first node, forming a circle. This can be singly or doubly linked.

Basic Operations on Linked Lists

Creation:
- Initialize an empty linked list or create a new node.
Insertion:
- At the beginning: Add a new node at the start.
- At the end: Add a new node at the end of the list.
- At a specific position: Insert a node at a given index.
Deletion:
- By value: Remove the first node containing the specified value.
- At a specific position: Remove a node at a specified index.
Traversal:
- Access each node in the list sequentially.
Searching:
- Find a node containing a specified value.
Modification:
- Update the value of a node at a specified position.
Size:
- Count the number of nodes in the list.
Clear:
- Remove all nodes from the list.

Example of a Singly Linked List Implementation in C

Here’s a simple implementation of a singly linked list in C that supports basic operations:

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

// Definition of a node in the linked list
typedef struct Node {
int data;
struct Node* next;
} Node;

// Function to create a new node
Node* createNode(int value) {
Node* newNode = (Node*)malloc(sizeof(Node));
newNode->data = value;
newNode->next = NULL;
return newNode;
}

// Function to insert a node at the beginning
void insertAtBeginning(Node** head, int value) {
Node* newNode = createNode(value);
newNode->next = *head;
*head = newNode;
}

// Function to insert a node at the end
void insertAtEnd(Node** head, int value) {
Node* newNode = createNode(value);
if (*head == NULL) {
*head = newNode;
return;
}
Node* temp = *head;
while (temp->next != NULL) {
temp = temp->next;
}
temp->next = newNode;
}

// Function to delete a node by value
void deleteNode(Node** head, int value) {
Node* temp = *head;
Node* prev = NULL;

// If the node to be deleted is the head
if (temp != NULL && temp->data == value) {
*head = temp->next;
free(temp);
return;
}

// Search for the node to be deleted
while (temp != NULL && temp->data != value) {
prev = temp;
temp = temp->next;
}

// If the value was not found
if (temp == NULL) {
printf(“Value %d not found in the list.\n”, value);
return;
}

// Unlink the node
prev->next = temp->next;
free(temp);
}

// Function to traverse the list
void traverseList(Node* head) {
Node* temp = head;
printf(“Linked List: “);
while (temp != NULL) {
printf(“%d -> “, temp->data);
temp = temp->next;
}
printf(“NULL\n”);
}

// Function to search for a value in the list
int searchList(Node* head, int value) {
Node* temp = head;
while (temp != NULL) {
if (temp->data == value) {
return 1; // Value found
}
temp = temp->next;
}
return 0; // Value not found
}

// Main function to demonstrate the linked list operations
int main() {
Node* head = NULL; // Initialize an empty list

// Inserting elements
insertAtBeginning(&head, 10);
insertAtBeginning(&head, 20);
insertAtEnd(&head, 30);
insertAtEnd(&head, 40);

// Traversing the list
traverseList(head);

// Searching for a value
int searchValue = 20;
if (searchList(head, searchValue)) {
printf(“%d found in the list.\n”, searchValue);
} else {
printf(“%d not found in the list.\n”, searchValue);
}

// Deleting a value
deleteNode(&head, 20);
traverseList(head);

// Clean up memory
deleteNode(&head, 10);
deleteNode(&head, 30);
deleteNode(&head, 40);

return 0;
}

Explanation of the Code

Node Structure: Each node contains an integer data field and a pointer next to the next node.
Creating a Node: The createNode function allocates memory for a new node and initializes its data.
Insertion Functions:
- insertAtBeginning: Inserts a new node at the start of the list.
- insertAtEnd: Inserts a new node at the end of the list.
Deletion Function:
- deleteNode: Searches for a specified value and removes it from the list.
Traversal Function:
- traverseList: Prints all values in the list.
Search Function:
- searchList: Checks if a specific value exists in the list.
Main Function: Demonstrates the various operations of the linked list.

How to Compile and Run

Copy the complete code into a .c file (e.g., singly_linked_list.c).
Open a terminal and navigate to the directory containing the file.
Compile the program using:

gcc singly_linked_list.c -o singly_linked_list
Run the program with:

./singly_linked_list

This implementation creates a simple singly linked list, allowing you to perform various operations and see the output for each operation.

Advantages of Linked Lists

Dynamic Size: Can grow or shrink as needed.
Efficient Insertions/Deletions: Particularly at the beginning or end without needing to shift elements.
No Wasted Space: Memory is allocated only when needed.

Limitations of Linked Lists

Memory Overhead: Each node requires additional memory for storing pointers.
Sequential Access: Must traverse from the head to access elements, leading to O(n) access time.
Cache Locality: Non-contiguous memory allocation can lead to poor cache performance.

4.4 Types of Linked List: Singly Linked List, Doubly Linked List, Circular Linked List.

Linked lists are versatile data structures that can be implemented in several forms. The three most common types of linked lists are:

Singly Linked List
Doubly Linked List
Circular Linked List

Each type has its unique structure, advantages, and use cases.

1. Singly Linked List

Definition: A singly linked list consists of nodes, where each node contains data and a pointer to the next node in the sequence. It allows for traversal in one direction—from the head to the end of the list.

Structure:

Head -> [Data | Next] -> [Data | Next] -> [Data | Next] -> NULL

Operations:

Insertion: At the beginning, end, or specific position.
Deletion: By value or at a specific position.
Traversal: Access each node sequentially.

Advantages:

Simple and easy to implement.
Efficient memory usage compared to arrays for dynamic sizes.

Disadvantages:

Only allows traversal in one direction.
Searching for elements can be O(n) time complexity.

2. Doubly Linked List

Definition: A doubly linked list consists of nodes, where each node contains data, a pointer to the next node, and a pointer to the previous node. This allows traversal in both directions—forward and backward.

Structure:

Operations:

Insertion: At the beginning, end, or specific position.
Deletion: By value or at a specific position.
Traversal: Access each node in both directions.

Advantages:

Bidirectional traversal is possible.
Easier to delete a node when given a pointer to it.

Disadvantages:

Requires more memory due to extra pointers (prev and next).
Slightly more complex to implement than singly linked lists.

3. Circular Linked List

Definition: A circular linked list can be singly or doubly linked, where the last node points back to the first node, forming a circle. This structure can be beneficial for certain applications that require cyclic traversal.

Structure (Singly Circular Linked List):

Head -> [Data | Next] -> [Data | Next] -> [Data | Next] –+
^ |
+———————————————-+

Operations:

Insertion: Similar to singly linked lists, but ensures the last node points back to the head.
Deletion: Similar to singly linked lists, but careful handling is needed for the head and tail.
Traversal: Continues until it returns to the starting node.

Advantages:

No NULL values, which can simplify some algorithms (e.g., finding the end of the list).
Can easily loop through the list indefinitely without special cases.

Disadvantages:

More complex to manage compared to standard linked lists.
Can lead to infinite loops if not handled correctly during traversal.

Summary of Comparison

Feature	Singly Linked List	Doubly Linked List	Circular Linked List
Direction	One-way	Two-way	One-way or two-way
Memory Overhead	Low	Higher (extra pointer)	Moderate
Traversal Complexity	O(n)	O(n)	O(n)
Insertion Complexity	O(1) (at head)	O(1) (at head)	O(1) (at head)
Deletion Complexity	O(n)	O(n)	O(n)
Use Cases	Simple lists	Complex data structures, navigation	Round-robin scheduling, buffer management

4.5 Basic operations in Linked List: creation, node insertion and deletion from beginning, end and specified position

Linked lists provide several fundamental operations to manage the nodes effectively. The primary operations include creation, node insertion, and deletion. Here’s an overview of these operations with examples for both singly linked lists and doubly linked lists.

1. Creation of a Linked List

Definition: The creation of a linked list involves initializing an empty list and creating nodes to populate it.

Singly Linked List Creation:

typedef struct Node {
int data;
struct Node* next;
} Node;

Node* createNode(int value) {
Node* newNode = (Node*)malloc(sizeof(Node));
newNode->data = value;
newNode->next = NULL;
return newNode;
}

2. Node Insertion

Node insertion involves adding a new node to the list. The insertion can occur at three primary positions: the beginning, the end, or a specified position.

a. Insertion at the Beginning

Singly Linked List:

void insertAtBeginning(Node** head, int value) {
Node* newNode = createNode(value);
newNode->next = *head;
*head = newNode;
}

Doubly Linked List:

typedef struct DNode {
int data;
struct DNode* next;
struct DNode* prev;
} DNode;

void insertAtBeginning(DNode** head, int value) {
DNode* newNode = (DNode*)malloc(sizeof(DNode));
newNode->data = value;
newNode->next = *head;
newNode->prev = NULL;

if (*head != NULL) {
(*head)->prev = newNode;
}
*head = newNode;
}

b. Insertion at the End

Singly Linked List:

void insertAtEnd(Node** head, int value) {
Node* newNode = createNode(value);
if (*head == NULL) {
*head = newNode;
return;
}
Node* temp = *head;
while (temp->next != NULL) {
temp = temp->next;
}
temp->next = newNode;
}

Doubly Linked List:

void insertAtEnd(DNode** head, int value) {
DNode* newNode = (DNode*)malloc(sizeof(DNode));
newNode->data = value;
newNode->next = NULL;

if (*head == NULL) {
newNode->prev = NULL;
*head = newNode;
return;
}
DNode* temp = *head;
while (temp->next != NULL) {
temp = temp->next;
}
temp->next = newNode;
newNode->prev = temp;
}

c. Insertion at a Specified Position

Singly Linked List:

void insertAtPosition(Node** head, int value, int position) {
Node* newNode = createNode(value);
if (position == 0) {
insertAtBeginning(head, value);
return;
}
Node* temp = *head;
for (int i = 0; temp != NULL && i < position – 1; i++) {
temp = temp->next;
}
if (temp == NULL) {
printf(“Position is out of bounds.\n”);
return;
}
newNode->next = temp->next;
temp->next = newNode;
}

Doubly Linked List:

void insertAtPosition(DNode** head, int value, int position) {
DNode* newNode = (DNode*)malloc(sizeof(DNode));
newNode->data = value;

if (position == 0) {
insertAtBeginning(head, value);
return;
}

DNode* temp = *head;
for (int i = 0; temp != NULL && i < position – 1; i++) {
temp = temp->next;
}
if (temp == NULL) {
printf(“Position is out of bounds.\n”);
return;
}

newNode->next = temp->next;
newNode->prev = temp;

if (temp->next != NULL) {
temp->next->prev = newNode;
}
temp->next = newNode;
}

3. Node Deletion

Node deletion involves removing a node from the linked list. Deletion can occur from the beginning, the end, or a specified position.

a. Deletion from the Beginning

Singly Linked List:

void deleteFromBeginning(Node** head) {
if (*head == NULL) return; // List is empty
Node* temp = *head;
*head = (*head)->next;
free(temp);
}

Doubly Linked List:

void deleteFromBeginning(DNode** head) {
if (*head == NULL) return; // List is empty
DNode* temp = *head;
*head = (*head)->next;
if (*head != NULL) {
(*head)->prev = NULL;
}
free(temp);
}

b. Deletion from the End

Singly Linked List:

void deleteFromEnd(Node** head) {
if (*head == NULL) return; // List is empty
Node* temp = *head;
if (temp->next == NULL) {
free(temp);
*head = NULL;
return;
}
while (temp->next->next != NULL) {
temp = temp->next;
}
free(temp->next);
temp->next = NULL;
}

Doubly Linked List:

void deleteFromEnd(DNode** head) {
if (*head == NULL) return; // List is empty
DNode* temp = *head;
if (temp->next == NULL) {
free(temp);
*head = NULL;
return;
}
while (temp->next != NULL) {
temp = temp->next;
}
temp->prev->next = NULL;
free(temp);
}

c. Deletion from a Specified Position

Singly Linked List:

void deleteAtPosition(Node** head, int position) {
if (*head == NULL) return; // List is empty
Node* temp = *head;

if (position == 0) {
deleteFromBeginning(head);
return;
}

for (int i = 0; temp != NULL && i < position – 1; i++) {
temp = temp->next;
}

if (temp == NULL || temp->next == NULL) {
printf(“Position is out of bounds.\n”);
return;
}

Node* nextNode = temp->next->next;
free(temp->next);
temp->next = nextNode;
}

Doubly Linked List:

void deleteAtPosition(DNode** head, int position) {
if (*head == NULL) return; // List is empty
DNode* temp = *head;

if (position == 0) {
deleteFromBeginning(head);
return;
}

for (int i = 0; temp != NULL && i < position; i++) {
temp = temp->next;
}

if (temp == NULL) {
printf(“Position is out of bounds.\n”);
return;
}

if (temp->next != NULL) {
temp->next->prev = temp->prev;
}
if (temp->prev != NULL) {
temp->prev->next = temp->next;
}
free(temp);
}

Summary of Basic Operations

Creation: Initialize a linked list and create nodes.
Insertion:
- At the beginning.
- At the end.
- At a specified position.
Deletion:
- From the beginning.
- From the end.
- At a specified position.

4.6 Stack and Queue as a Linked List

Both stacks and queues can be efficiently implemented using linked lists. This approach allows for dynamic memory allocation, meaning that the size of the stack or queue can grow and shrink as needed without the limitations of a fixed-size array.

1. Stack as a Linked List

A stack is a Last In, First Out (LIFO) data structure where the last element added is the first one to be removed. When implementing a stack using a linked list, each node contains data and a pointer to the next node.

Node Structure:

typedef struct Node {
int data;
struct Node* next;
} Node;

Stack Structure:

typedef struct Stack {
Node* top;
} Stack;

Stack Operations:

Create a Stack:

Stack* createStack() {
Stack* stack = (Stack*)malloc(sizeof(Stack));
stack->top = NULL;
return stack;
}

Push (Insert an Element):

void push(Stack* stack, int value) {
Node* newNode = (Node*)malloc(sizeof(Node));
newNode->data = value;
newNode->next = stack->top;
stack->top = newNode;
}

Pop (Remove an Element):

int pop(Stack* stack) {
if (stack->top == NULL) {
printf(“Stack Underflow\n”);
return -1; // Indicating stack is empty
}
Node* temp = stack->top;
int poppedValue = temp->data;
stack->top = stack->top->next;
free(temp);
return poppedValue;
}

Peek (Get the Top Element):

int peek(Stack* stack) {
if (stack->top == NULL) {
printf(“Stack is empty\n”);
return -1; // Indicating stack is empty
}
return stack->top->data;
}

2. Queue as a Linked List

A queue is a First In, First Out (FIFO) data structure where the first element added is the first one to be removed. When implementing a queue using a linked list, each node contains data and pointers to both the next node and the previous node.

Node Structure:

typedef struct Node {
int data;
struct Node* next;
} Node;

Queue Structure:

Queue* createQueue() {
Queue* queue = (Queue*)malloc(sizeof(Queue));
queue->front = queue->rear = NULL;
return queue;
}

Queue Operations:

Create a Queue:

Queue* createQueue() {
Queue* queue = (Queue*)malloc(sizeof(Queue));
queue->front = queue->rear = NULL;
return queue;
}

Enqueue (Insert an Element):

void enqueue(Queue* queue, int value) {
Node* newNode = (Node*)malloc(sizeof(Node));
newNode->data = value;
newNode->next = NULL;

if (queue->rear == NULL) {
queue->front = queue->rear = newNode;
return;
}
queue->rear->next = newNode;
queue->rear = newNode;
}

Dequeue (Remove an Element):

int dequeue(Queue* queue) {
if (queue->front == NULL) {
printf(“Queue Underflow\n”);
return -1; // Indicating queue is empty
}
Node* temp = queue->front;
int dequeuedValue = temp->data;
queue->front = queue->front->next;

if (queue->front == NULL) {
queue->rear = NULL; // If the queue becomes empty
}
free(temp);
return dequeuedValue;
}

Peek (Get the Front Element):

int peekQueue(Queue* queue) {
if (queue->front == NULL) {
printf(“Queue is empty\n”);
return -1; // Indicating queue is empty
}
return queue->front->data;
}

Summary of Stack and Queue Implementations

Stack:
- LIFO behavior implemented using a linked list.
- Supports operations: push, pop, and peek.
Queue:
- FIFO behavior implemented using a linked list.
- Supports operations: enqueue, dequeue, and peek

Write a program to implement singly and doubly linked list operations

Below is a C program that implements basic operations for both singly and doubly linked lists. The operations include creating a list, inserting nodes at the beginning, end, and a specified position, as well as deleting nodes from the beginning, end, and a specified position.

C Program for Singly Linked List and Doubly Linked List Operations

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

// Singly Linked List Node Definition
typedef struct SinglyNode {
int data;
struct SinglyNode* next;
} SinglyNode;

// Doubly Linked List Node Definition
typedef struct DoublyNode {
int data;
struct DoublyNode* next;
struct DoublyNode* prev;
} DoublyNode;

// Function Prototypes for Singly Linked List
SinglyNode* createSinglyNode(int value);
void insertAtBeginningSingly(SinglyNode** head, int value);
void insertAtEndSingly(SinglyNode** head, int value);
void insertAtPositionSingly(SinglyNode** head, int value, int position);
void deleteFromBeginningSingly(SinglyNode** head);
void deleteFromEndSingly(SinglyNode** head);
void deleteAtPositionSingly(SinglyNode** head, int position);
void displaySingly(SinglyNode* head);

// Function Prototypes for Doubly Linked List
DoublyNode* createDoublyNode(int value);
void insertAtBeginningDoubly(DoublyNode** head, int value);
void insertAtEndDoubly(DoublyNode** head, int value);
void insertAtPositionDoubly(DoublyNode** head, int value, int position);
void deleteFromBeginningDoubly(DoublyNode** head);
void deleteFromEndDoubly(DoublyNode** head);
void deleteAtPositionDoubly(DoublyNode** head, int position);
void displayDoubly(DoublyNode* head);

int main() {
SinglyNode* singlyHead = NULL;
DoublyNode* doublyHead = NULL;

// Singly Linked List Operations
printf(“Singly Linked List Operations:\n”);
insertAtEndSingly(&singlyHead, 10);
insertAtEndSingly(&singlyHead, 20);
insertAtBeginningSingly(&singlyHead, 5);
insertAtPositionSingly(&singlyHead, 15, 2);
displaySingly(singlyHead);

deleteFromBeginningSingly(&singlyHead);
displaySingly(singlyHead);
deleteFromEndSingly(&singlyHead);
displaySingly(singlyHead);
deleteAtPositionSingly(&singlyHead, 1);
displaySingly(singlyHead);

// Doubly Linked List Operations
printf(“\nDoubly Linked List Operations:\n”);
insertAtEndDoubly(&doublyHead, 100);
insertAtEndDoubly(&doublyHead, 200);
insertAtBeginningDoubly(&doublyHead, 50);
insertAtPositionDoubly(&doublyHead, 150, 2);
displayDoubly(doublyHead);

deleteFromBeginningDoubly(&doublyHead);
displayDoubly(doublyHead);
deleteFromEndDoubly(&doublyHead);
displayDoubly(doublyHead);
deleteAtPositionDoubly(&doublyHead, 1);
displayDoubly(doublyHead);

return 0;
}

// Singly Linked List Functions
SinglyNode* createSinglyNode(int value) {
SinglyNode* newNode = (SinglyNode*)malloc(sizeof(SinglyNode));
newNode->data = value;
newNode->next = NULL;
return newNode;
}

void insertAtBeginningSingly(SinglyNode** head, int value) {
SinglyNode* newNode = createSinglyNode(value);
newNode->next = *head;
*head = newNode;
}

void insertAtEndSingly(SinglyNode** head, int value) {
SinglyNode* newNode = createSinglyNode(value);
if (*head == NULL) {
*head = newNode;
return;
}
SinglyNode* temp = *head;
while (temp->next != NULL) {
temp = temp->next;
}
temp->next = newNode;
}

void insertAtPositionSingly(SinglyNode** head, int value, int position) {
SinglyNode* newNode = createSinglyNode(value);
if (position == 0) {
insertAtBeginningSingly(head, value);
return;
}
SinglyNode* temp = *head;
for (int i = 0; temp != NULL && i < position – 1; i++) {
temp = temp->next;
}
if (temp == NULL) {
printf(“Position is out of bounds.\n”);
return;
}
newNode->next = temp->next;
temp->next = newNode;
}

void deleteFromBeginningSingly(SinglyNode** head) {
if (*head == NULL) return; // List is empty
SinglyNode* temp = *head;
*head = (*head)->next;
free(temp);
}

void deleteFromEndSingly(SinglyNode** head) {
if (*head == NULL) return; // List is empty
SinglyNode* temp = *head;
if (temp->next == NULL) {
free(temp);
*head = NULL;
return;
}
while (temp->next->next != NULL) {
temp = temp->next;
}
free(temp->next);
temp->next = NULL;
}

void deleteAtPositionSingly(SinglyNode** head, int position) {
if (*head == NULL) return; // List is empty
SinglyNode* temp = *head;

if (position == 0) {
deleteFromBeginningSingly(head);
return;
}

for (int i = 0; temp != NULL && i < position – 1; i++) {
temp = temp->next;
}

if (temp == NULL || temp->next == NULL) {
printf(“Position is out of bounds.\n”);
return;
}

SinglyNode* nextNode = temp->next->next;
free(temp->next);
temp->next = nextNode;
}

void displaySingly(SinglyNode* head) {
if (head == NULL) {
printf(“Singly Linked List is empty.\n”);
return;
}
SinglyNode* temp = head;
printf(“Singly Linked List: “);
while (temp != NULL) {
printf(“%d -> “, temp->data);
temp = temp->next;
}
printf(“NULL\n”);
}

// Doubly Linked List Functions
DoublyNode* createDoublyNode(int value) {
DoublyNode* newNode = (DoublyNode*)malloc(sizeof(DoublyNode));
newNode->data = value;
newNode->next = NULL;
newNode->prev = NULL;
return newNode;
}

void insertAtBeginningDoubly(DoublyNode** head, int value) {
DoublyNode* newNode = createDoublyNode(value);
newNode->next = *head;
newNode->prev = NULL;

if (*head != NULL) {
(*head)->prev = newNode;
}
*head = newNode;
}

void insertAtEndDoubly(DoublyNode** head, int value) {
DoublyNode* newNode = createDoublyNode(value);
if (*head == NULL) {
*head = newNode;
return;
}
DoublyNode* temp = *head;
while (temp->next != NULL) {
temp = temp->next;
}
temp->next = newNode;
newNode->prev = temp;
}

void insertAtPositionDoubly(DoublyNode** head, int value, int position) {
DoublyNode* newNode = createDoublyNode(value);
if (position == 0) {
insertAtBeginningDoubly(head, value);
return;
}
DoublyNode* temp = *head;
for (int i = 0; temp != NULL && i < position – 1; i++) {
temp = temp->next;
}
if (temp == NULL) {
printf(“Position is out of bounds.\n”);
return;
}

newNode->next = temp->next;
newNode->prev = temp;

if (temp->next != NULL) {
temp->next->prev = newNode;
}
temp->next = newNode;
}

void deleteFromBeginningDoubly(DoublyNode** head) {
if (*head == NULL) return; // List is empty
DoublyNode* temp = *head;
*head = (*head)->next;
if (*head != NULL) {
(*head)->prev = NULL;
}
free(temp);
}

void deleteFromEndDoubly(DoublyNode** head) {
if (*head == NULL) return; // List is empty
DoublyNode* temp = *head;
if (temp->next == NULL) {
free(temp);
*head = NULL;
return;
}
while (temp->next != NULL) {
temp = temp->next;

Write a program to implement stack and queue as linked list.

Here’s a C program that implements both stack and queue using linked lists. The stack follows the Last In, First Out (LIFO) principle, while the queue follows the First In, First Out (FIFO) principle.

C Program to Implement Stack and Queue as Linked List

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

// Stack Node Definition
typedef struct StackNode {
int data;
struct StackNode* next;
} StackNode;

// Queue Node Definition
typedef struct QueueNode {
int data;
struct QueueNode* next;
} QueueNode;

// Stack Functions
StackNode* createStackNode(int value);
void push(StackNode** top, int value);
int pop(StackNode** top);
int peek(StackNode* top);
int isStackEmpty(StackNode* top);
void displayStack(StackNode* top);

// Queue Functions
QueueNode* createQueueNode(int value);
void enqueue(QueueNode** front, QueueNode** rear, int value);
int dequeue(QueueNode** front);
int peekQueue(QueueNode* front);
int isQueueEmpty(QueueNode* front);
void displayQueue(QueueNode* front);

int main() {
// Stack Operations
StackNode* stackTop = NULL;

printf(“Stack Operations:\n”);
push(&stackTop, 10);
push(&stackTop, 20);
push(&stackTop, 30);
displayStack(stackTop);

printf(“Popped: %d\n”, pop(&stackTop));
displayStack(stackTop);
printf(“Top element: %d\n”, peek(stackTop));

// Queue Operations
QueueNode* queueFront = NULL;
QueueNode* queueRear = NULL;

printf(“\nQueue Operations:\n”);
enqueue(&queueFront, &queueRear, 100);
enqueue(&queueFront, &queueRear, 200);
enqueue(&queueFront, &queueRear, 300);
displayQueue(queueFront);

printf(“Dequeued: %d\n”, dequeue(&queueFront));
displayQueue(queueFront);
printf(“Front element: %d\n”, peekQueue(queueFront));

return 0;
}

// Stack Functions Implementation
StackNode* createStackNode(int value) {
StackNode* newNode = (StackNode*)malloc(sizeof(StackNode));
newNode->data = value;
newNode->next = NULL;
return newNode;
}

void push(StackNode** top, int value) {
StackNode* newNode = createStackNode(value);
newNode->next = *top;
*top = newNode;
}

int pop(StackNode** top) {
if (isStackEmpty(*top)) {
printf(“Stack Underflow\n”);
return -1; // Indicates that the stack is empty
}
StackNode* temp = *top;
int poppedValue = temp->data;
*top = (*top)->next;
free(temp);
return poppedValue;
}

int peek(StackNode* top) {
if (isStackEmpty(top)) {
printf(“Stack is empty\n”);
return -1; // Indicates that the stack is empty
}
return top->data;
}

int isStackEmpty(StackNode* top) {
return top == NULL;
}

void displayStack(StackNode* top) {
if (isStackEmpty(top)) {
printf(“Stack is empty\n”);
return;
}
StackNode* temp = top;
printf(“Stack: “);
while (temp != NULL) {
printf(“%d -> “, temp->data);
temp = temp->next;
}
printf(“NULL\n”);
}

// Queue Functions Implementation
QueueNode* createQueueNode(int value) {
QueueNode* newNode = (QueueNode*)malloc(sizeof(QueueNode));
newNode->data = value;
newNode->next = NULL;
return newNode;
}

void enqueue(QueueNode** front, QueueNode** rear, int value) {
QueueNode* newNode = createQueueNode(value);
if (*rear == NULL) {
*front = *rear = newNode;
return;
}
(*rear)->next = newNode;
*rear = newNode;
}

int dequeue(QueueNode** front) {
if (isQueueEmpty(*front)) {
printf(“Queue Underflow\n”);
return -1; // Indicates that the queue is empty
}
QueueNode* temp = *front;
int dequeuedValue = temp->data;
*front = (*front)->next;

if (*front == NULL) {
// If the queue becomes empty
printf(“Queue is now empty\n”);
}

free(temp);
return dequeuedValue;
}

int peekQueue(QueueNode* front) {
if (isQueueEmpty(front)) {
printf(“Queue is empty\n”);
return -1; // Indicates that the queue is empty
}
return front->data;
}

int isQueueEmpty(QueueNode* front) {
return front == NULL;
}

void displayQueue(QueueNode* front) {
if (isQueueEmpty(front)) {
printf(“Queue is empty\n”);
return;
}
QueueNode* temp = front;
printf(“Queue: “);
while (temp != NULL) {
printf(“%d -> “, temp->data);
temp = temp->next;
}
printf(“NULL\n”);
}

Explanation of the Program

Data Structures:
- StackNode: Structure to represent a node in the stack.
- QueueNode: Structure to represent a node in the queue.
Stack Operations:
- createStackNode: Allocates memory for a new stack node.
- push: Inserts a new node at the top of the stack.
- pop: Removes and returns the top node from the stack.
- peek: Returns the data of the top node without removing it.
- isStackEmpty: Checks if the stack is empty.
- displayStack: Displays all elements in the stack.
Queue Operations:
- createQueueNode: Allocates memory for a new queue node.
- enqueue: Inserts a new node at the end of the queue.
- dequeue: Removes and returns the front node from the queue.
- peekQueue: Returns the data of the front node without removing it.
- isQueueEmpty: Checks if the queue is empty.
- displayQueue: Displays all elements in the queue.

Output Example

When you run the program, you will see output similar to this:

Stack Operations:
Stack: 30 -> 20 -> 10 -> NULL
Popped: 30
Stack: 20 -> 10 -> NULL
Top element: 20

Queue Operations:
Queue: 100 -> 200 -> 300 -> NULL
Dequeued: 100
Queue: 200 -> 300 -> NULL
Front element: 200

Lists

Lists

4.1 List and ADT

What is a List?

Characteristics of Lists

What is an Abstract Data Type (ADT)?

Lists as an ADT

Advantages of Using Lists as ADTs

Example of List ADT Operations

4.2 Array Implementation of Lists

Characteristics of Array Implementation

Basic Operations on Array-Backed Lists

Example of Array Implementation in C

Explanation of the Code

How to Compile and Run

4.3 Linked List

Characteristics of Linked Lists

Basic Operations on Linked Lists

Example of a Singly Linked List Implementation in C

Explanation of the Code

How to Compile and Run

Advantages of Linked Lists

Limitations of Linked Lists

4.4 Types of Linked List: Singly Linked List, Doubly Linked List, Circular Linked List.

1. Singly Linked List

2. Doubly Linked List

3. Circular Linked List

Summary of Comparison

4.5 Basic operations in Linked List: creation, node insertion and deletion from beginning, end and specified position

1. Creation of a Linked List

2. Node Insertion

a. Insertion at the Beginning

b. Insertion at the End

c. Insertion at a Specified Position

3. Node Deletion

a. Deletion from the Beginning

b. Deletion from the End

c. Deletion from a Specified Position

Summary of Basic Operations

4.6 Stack and Queue as a Linked List

1. Stack as a Linked List

2. Queue as a Linked List

Summary of Stack and Queue Implementations

Write a program to implement singly and doubly linked list operations

C Program for Singly Linked List and Doubly Linked List Operations

Write a program to implement stack and queue as linked list.

C Program to Implement Stack and Queue as Linked List

Explanation of the Program

Output Example

Discussion