Linked List

Why we need a Linked List

What is a linked list?

In code a node is just those two fields:

class Node {  int data;     // the value  Node next;    // where the next node is, or null at the end}

How do you reach an element?

A linked list does not have indexes like an array. To reach 30 you start at head and follow the links: first 10, then 20, then 30. This is called traversal.

So finding an element can take O(n) time, because you may have to walk through the whole list. An array can jump straight to an index in O(1).

Run search a few times. When the value is there it stops early, and when it is not, cur walks all the way to NULL before it can say so. Then run insert and watch how little moves.

Why not just use an array?

An array stores its elements next to each other, so inserting one in the middle means shifting everything after it along to open a gap.

A linked list does not shift anything. It changes the links.

The trade-off is simple:

• Array: fast access
• Linked list: easier insert and delete

Insertion: change the links

Suppose we want to insert 15 between 10 and 20.

We do not move 20 or 30. We just connect the nodes correctly. That is the whole idea behind insertion in a linked list.

Deletion: skip a node

Suppose we want to remove 20. We make 10 point directly at 30.

20 is no longer part of the list, and again, nothing else has to shift.

The head is important

head points to the first node. If you lose head, you lose access to the entire list.

So when traversing, do not move head itself. Use another variable, current = head, and move that through the list instead.

Types of linked lists

There are three common types.

• Singly linked list: each node points only to the next node.
• Doubly linked list: each node points to both the previous and the next node, so you can move in both directions.
• Circular linked list: the last node points back to the first, so the list forms a circle.

Linked list vs array

Where are linked lists used?

Linked lists are useful when elements need to be connected and changed often.

• Music playlists: move between songs
• Browser history: move between previous and next pages
• Undo and redo: move between states
• Stacks and queues: both can be built out of linked lists
• Hash tables: a linked list can hold the items that land in the same bucket

You may not reach for a linked list every day, but the idea of nodes connected by links turns up inside many other data structures.

Common mistakes

• Forgetting to handle an empty list
• Losing the next node while changing links
• Moving head while traversing
• Trying to reach a node by index, like list[3]
• Forgetting that the last node points to null
• Assuming a linked list is always better than an array

A linked list is useful for specific situations. It is not automatically better than an array.

Quick recap

A linked list is a chain of nodes. Each node stores a value and a link to the next node.

• head points to the first node
• The last node points to null
• Access is slow, O(n), because you have to walk
• Insert and delete are easy once you are at the right node