LEARNING OUTCOME 6

Linked List

A linked list is a linear data structure where elements are not stored in contiguous memory locations. Instead, each element, called a node, contains data and a pointer to the next node in the sequence. This allows for dynamic memory allocation and efficient insertion and deletion of elements, especially when compared to arrays.

Array-based List vs. Linked List

Feature	Array-Based List	Linked List
Memory Allocation	Contiguous memory allocation	Dynamic memory allocation
Access to Elements	Direct access using index (O(1))	Sequential access through pointers (O(n))
Insertion and Deletion	Inefficient (O(n)), requires shifting elements	Efficient (O(1)) if pointer to node is known
Space Overhead	Minimal overhead	Additional memory for pointers
Flexibility in Size	Fixed size	Dynamic size
Cache Efficiency	Generally more cache-friendly	Less cache-friendly due to non-contiguous memory

Types of Linked Lists

Singly Linked List: Each node contains data and a pointer to the next node. It allows traversal in one direction only, from the head to the tail.
Doubly Linked List: Each node contains data, a pointer to the next node, and a pointer to the previous node. This allows traversal in both directions.
Circular Linked List: The last node points back to the first node, forming a circular structure. This can be useful for certain algorithms and data structures.

Creating a Linked List

Defining the Node Structure

The fundamental building block of a linked list is the node. Each node contains:

data: The actual data stored in the node (can be any data type).
next: A pointer to the next node in the list. This pointer is what links the nodes together.

1
2
3
4
5
6
7

struct Node { int data; // Data stored in the node Node* next; // Pointer to the next node // Constructor to initialize a new node Node(int val) : data(val), next(nullptr) {} };

The LinkedList Class

To manage the linked list, it's good practice to create a `LinkedList` class. This class will encapsulate the operations you can perform on the list and hold a pointer to the first node (the `head`).

1
2
3
4
5
6
7
8

class LinkedList { private: Node* head; // Pointer to the first node in the list public: LinkedList() : head(nullptr) {} // Constructor: initially empty list // ... (Methods for operations will go here) };

Linked List Operations

Traversing and Displaying

To see the contents of the list, you traverse it from the `head`, following the `next` pointers until you reach `nullptr`.

1
2
3
4
5
6
7
8

void display() { Node* current = head; // Start from the head while (current != nullptr) { // Traverse until the end std::cout << current->data << " -> "; current = current->next; // Move to the next node } std::cout << "nullptr" << std::endl; }

Insertion

Nodes can be inserted at the beginning, middle, or end of the list.

Inserting at the Beginning

1
2
3
4
5

void insertAtBeginning(int data) { Node* newNode = new Node(data); // Create a new node newNode->next = head; // New node points to the current head head = newNode; // Head now points to the new node }

Inserting at the End

1
2
3
4
5
6
7
8
9
10
11
12

void insertAtEnd(int data) { Node* newNode = new Node(data); if (head == nullptr) { // If list is empty head = newNode; return; } Node* last = head; while (last->next != nullptr) { // Traverse to the last node last = last->next; } last->next = newNode; // Link the last node to the new node }

Deleting a Node

To delete a node, you must find it and then adjust the `next` pointer of the *previous* node to bypass the node being deleted.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

void deleteNode(int key) { Node* current = head; Node* prev = nullptr; // If head node holds the key if (current != nullptr && current->data == key) { head = current->next; delete current; return; } // Search for the key, keeping track of the previous node while (current != nullptr && current->data != key) { prev = current; current = current->next; } // If key was not found if (current == nullptr) return; // Unlink the node and free memory prev->next = current->next; delete current; }

Memory Management

It is crucial to deallocate memory for each node when the list is no longer needed to prevent memory leaks. This is typically done in the class destructor.

1
2
3
4
5
6
7
8
9

~LinkedList() { Node* current = head; while (current != nullptr) { Node* nextNode = current->next; delete current; current = nextNode; } head = nullptr; }

End of Outcome Quiz

1 of 20

Question text will load here.

Quiz Results

Score: 0%

Answered: 0 of 0

Correct: 0

DESIGN & ANALYSIS OF ALGORITHMS

Search Topics in this Outcome