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.

Penji Team

December 27th

View Profile

Get in Touch

Thanks! We'll reach out shortly.

Rate this post

You won't be taken from this page or asked to login

Thanks! We'll reach out shortly.