Complexity

NB: Remove at tail in SLL is O(n) because we can't reset a value of what the tail is, so we have to seek till the end of the list and find out what new tail is equal to.

Overview

Linked List are the simplest form of dynamic data structure. A linked list organises items sequentially, with each item storing a pointer to the next one.

Picture a linked list like a chain of paperclips linked together. It's quick to add another paperclip to the top or bottom. It's even quick to insert one in the middle—just disconnect the chain at the middle link, add the new paperclip, then reconnect the other half.

An item in a linked list is called a node.

The first node is called the head.

The last node is called the tail.

<aside> 💡 Unlike an array, consecutive items in a linked list are not necessarily next to each other in memory.

</aside>

<aside> ⚠️ Remember that when you're discussing a linkedList in an interview, you must understand whether it is a singly linked list or doubly linked list.

</aside>

Terminology

• Head: the first node in linked list
• Tail: the last node in linked list
• Pointer: Reference to another node
• Node: An object containing data pointer(s)

Strengths:

• Fast operations on the ends. Adding elements at either end of a linked list is O(1). Removing the first element is also O(1).
• Flexible size. There's no need to specify how many elements you're going to store ahead of time. You can keep adding elements as long as there's enough space on the machine.

Weaknesses: