Linked Lists

 

Intro

A very important data structure, that is often confusing to beginning CS students, is the linked list. Linked lists are a linear data structure, just like basic arrays. However, unlike an array, the linked list is not one large, continuous block in memory. Instead, each element in a linked list contains a pointer to the next element. Each element is “linked” to the next, hence the term “linked list.”

Linked Lists vs Arrays

This might seem confusing at first, but let’s start by contrasting a linked list with an array. In an array, each element is accessible by an index. In Image 1, we can see this clearly. If we want the value of element 3, we just call num[2]. This is because the elements are all stored contiguously in memory, so we can move down the array to find the element we want.

Image 1

Image 1

In a linked list, the elements are not contiguous. Rather, each element contains a pointer to the next element. Take a look at Image 2. If we want the value at B, we can’t just call num[1]. Instead, we follow the pointer head to get to A. Then, we follow the pointer of A to get to B, and there is our value.

Image 2

Image 2

Linked List Implementation

Why Linked Lists?

Although more complicated, the linked list is a very useful data structure. With a linked list, there is no cost to resizing. As such, we can append, insert, or delete elements in constant time. With an array, this same operation takes linear time. With large data sets, this is a huge difference.