Table of Contents

Vocabulary

Linked Lists Head Pointer Tail Pointer Data Next Pointer Append Prepend Insert Remove

What Are Linked Lists?

<aside> 💡 Linked Lists are a type of data structures that consists of nodes that are “linked” by pointers. All linked lists contain a head and a tail pointer. The head pointer points to the “head” or start of the list and the tail points to the last node of the list.

Each node in a linked lists contains data and a next pointer. Data is the item (which can be an int, string, etc.) in the list. The next pointer points to the next node in the linked list.

The last node’s next pointer will point to NULL to indicate the end of the list (since there are no nodes to refer to).

</aside>

Creating A Linked List

class Node {
	public:
		int data;
		Node* next;
}

class LinkedList {
	Node* head;
	Node* tail;
}

Exploring The Benefits Of Linked Lists

<aside> 💡 When it comes to arrays, because of their contiguous nature and fixed size performing operations such as appending an element can be costly in terms of memory. When appending to an array with a fixed size, all of the array elements would need to be copied into a new array alongside the appended element, which is memory inefficient.

Additionally, if an element were to be inserted to the middle or beginning of an array, all of the existing array elements would need to be moved over, leading to insertion operations having a runtime of $O(n)$.

The next section analyzes operations done on arrays (append(), prepend(), insert(), remove()) on linked lists. The runtime for each of these methods will be denoted in a chart.

</aside>

Linked List Operations

Appending To A Linked List

<aside> 💡 In contrast to an array, with a linked list, appending an element takes $O(1)$ time and requires 2 assignment operations:

1. Changing where the last node’s next pointer points to by having it point to the newly added node.
2. Changing where the tail points to by having it point to the new last node.

</aside>

append(LinkedList L, Node newNode) {
	if (L->head == NULL) {
		L->head = newNode;
		L->tail = newNode;
	} else {
		L->tail->next = newNode;
		L->tail = newNode;
	}
}

Prepending To A Linked List