A Linked List is, as the word implies, a list where the nodes are linked together.
Each node
contains data and a pointer. The way they are linked together is that each node points to where
in the memory the next node is placed.
Linked Lists
A linked list consists of nodes with some sort of data, and a pointer, or link, to the next node.
A big benefit with using linked lists is that nodes are stored wherever there is free space in
memory, the nodes do not have to be stored contiguously right after each other like elements
are stored in arrays. Another nice thing with linked lists is that when adding or removing nodes,
the rest of the nodes in the list do not have to be shifted.
Linked Lists vs Arrays
The easiest way to understand linked lists is perhaps by comparing linked lists with arrays.
Linked lists consist of nodes, and is a linear data structure we make ourselves, unlike arrays
which is an existing data structure in the programming language that we can use.
Nodes in a linked list store links to other nodes, but array elements do not need to store links to
other elements.
Computer Memory
To explain what linked lists are, and how linked lists are different from arrays, we need to
understand some basics about how computer memory works.
Computer memory is the storage your program uses when it is running. This is where your
variables, arrays and linked lists are stored.
Variables in Memory
Let's imagine that we want to store the integer "17" in a variable myNumber. For simplicity, let's
assume the integer is stored as two bytes (16 bits), and the address in memory
to myNumber is 0x7F25.
0x7F25 is actually the address to the first of the two bytes of memory where
the myNumber integer value is stored. When the computer goes to 0x7F25 to read an integer
value, it knows that it must read both the first and the second byte, since integers are two bytes
on this specific computer.
The image below shows how the variable myNumber = 17 is stored in memory.
The example above shows how an integer value is stored on the simple, but popular, Arduino
Uno microcontroller. This microcontroller has an 8 bit architecture with 16 bit address bus and
uses two bytes for integers and two bytes for memory addresses. For comparison, personal
computers and smart phones use 32 or 64 bits for integers and addresses, but the memory
works basically in the same way.
Arrays in Memory
To understand linked lists, it is useful to first know how arrays are stored in memory.
Elements in an array are stored contiguously in memory. That means that each element is
stored right after the previous element.
The image below shows how an array of integers myArray = *3,5,13,2+ is stored in memory. We
use a simple kind of memory here with two bytes for each integer, like in the previous example,
just to get the idea.
The computer has only got the address of the first byte of myArray, so to access the 3rd element
with code myArray*2+ the computer starts at 0x7F23 and jumps over the two first integers. The
computer knows that an integer is stored in two bytes, so it jumps 2x2 bytes forward
from 0x7F23 and reads value 13 starting at address 0x7F27.
When removing or inserting elements in an array, every element that comes after must be
either shifted up to make place for the new element, or shifted down to take the removed
element's place. Such shifting operations are time consuming and can cause problems in real-
time systems for example.
The image below shows how elements are shifted when an array element is removed.
Manipulating arrays is also something you must think about if you are programming in C, where
you have to explicitly move other elements when inserting or removing an element. In C this
does not happen in the background.
In C you also need to make sure that you have allocated enough space for the array to start
with, so that you can add more elements later.
You can read more about arrays on this previous DSA tutorial page.
Linked Lists in Memory
Instead of storing a collection of data as an array, we can create a linked list.
Linked lists are used in many scenarios, like dynamic data storage, stack and queue
implementation or graph representation, to mention some of them.
A linked list consists of nodes with some sort of data, and at least one pointer, or link, to other
nodes.
A big benefit with using linked lists is that nodes are stored wherever there is free space in
memory, the nodes do not have to be stored contiguously right after each other like elements
are stored in arrays. Another nice thing with linked lists is that when adding or removing nodes,
the rest of the nodes in the list do not have to be shifted.
The image below shows how a linked list can be stored in memory. The linked list has four nodes
with values 3, 5, 13 and 2, and each node has a pointer to the next node in the list.
Each node takes up four bytes. Two bytes are used to store an integer value, and two bytes are
used to store the address to the next node in the list. As mentioned before, how many bytes
that are needed to store integers and addresses depend on the architecture of the computer.
This example, like the previous array example, fits with a simple 8-bit microcontroller
architecture.
To make it easier to see how the nodes relate to each other, we will display nodes in a linked list
in a simpler way, less related to their memory location, like in the image below:
If we put the same four nodes from the previous example together using this new visualization,
it looks like this:
As you can see, the first node in a linked list is called the "Head", and the last node is called the
"Tail".
Unlike with arrays, the nodes in a linked list are not placed right after each other in memory.
This means that when inserting or removing a node, shifting of other nodes is not necessary, so
that is a good thing.
Something not so good with linked lists is that we cannot access a node directly like we can with
an array by just writing myArray*5+ for example. To get to node number 5 in a linked list, we
must start with the first node called "head", use that node's pointer to get to the next node, and
do so while keeping track of the number of nodes we have visited until we reach node number
5.
Learning about linked lists helps us to better understand concepts like memory allocation and
pointers.
Linked lists are also important to understand before learning about more complex data
structures such as trees and graphs, that can be implemented using linked lists.
Memory in Modern Computers
So far on this page we have used the memory in an 8 bit microcontroller as an example to keep
it simple and easier to understand.
Memory in modern computers work in the same way in principle as memory in an 8 bit
microcontroller, but more memory is used to store integers, and more memory is used to store
memory addresses.
The code below gives us the size of an integer and the size of a memory address on the server
we are running these examples on.
#include <stdio.h>
int main() ,
int myVal = 13;
printf("Value of integer 'myVal': %d\n", myVal);
printf("Size of integer 'myVal': %lu bytes\n", sizeof(myVal)); // 4 bytes
printf("Address to 'myVal': %p\n", &myVal);
printf("Size of the address to 'myVal': %lu bytes\n", sizeof(&myVal)); // 8 bytes
return 0;
Types of Linked Lists
There are three basic forms of linked lists:
1. Singly linked lists
2. Doubly linked lists
3. Circular linked lists
A singly linked list is the simplest kind of linked lists. It takes up less space in memory because
each node has only one address to the next node, like in the image below.
A doubly linked list has nodes with addresses to both the previous and the next node, like in
the image below, and therefore takes up more memory. But doubly linked lists are good if you
want to be able to move both up and down in the list.
A circular linked list is like a singly or doubly linked list with the first node, the "head", and the
last node, the "tail", connected.
In singly or doubly linked lists, we can find the start and end of a list by just checking if the links
are null. But for circular linked lists, more complex code is needed to explicitly check for start
and end nodes in certain applications.
Circular linked lists are good for lists you need to cycle through continuously.
The image below is an example of a singly circular linked list:
The image below is an example of a doubly circular linked list:
Note: What kind of linked list you need depends on the problem you are trying to solve.
Linked List Implementations
Below are basic implementations of:
1. Singly linked list
2. Doubly linked list
3. Circular singly linked list
4. Circular doubly linked list
The next page will cover different operations that can be done on linked lists.
1. Singly Linked List Implementation
Below is an implementation of this singly linked list:
#include <stdio.h>
#include <stdlib.h>
// Define the Node struct
typedef struct Node ,
int data;
struct Node* next;
- Node;
// Create a new node
Node* createNode(int data) ,
Node* newNode = (Node*)malloc(sizeof(Node));
if (!newNode) ,
printf("Memory allocation failed!\n");
exit(1);
newNode->data = data;
newNode->next = NULL;
return newNode;
-
// Print the linked list
void printList(Node* node) ,
while (node) ,
printf("%d -> ", node->data);
node = node->next;
printf("null\n");
int main() ,
// Explicitly creating and connecting nodes
Node* node1 = createNode(3);
Node* node2 = createNode(5);
Node* node3 = createNode(13);
Node* node4 = createNode(2);
node1->next = node2;
node2->next = node3;
node3->next = node4;
printList(node1);
// Free the memory
free(node1);
free(node2);
free(node3);
free(node4);
return 0;
2. Doubly Linked List Implementation
Below is an implementation of this doubly linked list:
#include <stdio.h>
#include <stdlib.h>
typedef struct Node ,
int data;
struct Node* next;
struct Node* prev;
- Node;
int main() ,
Node* node1 = (Node*) malloc(sizeof(Node));
node1->data = 3;
node1->next = NULL;
node1->prev = NULL;
Node* node2 = (Node*) malloc(sizeof(Node));
node2->data = 5;
node2->next = NULL;
node2->prev = node1;
node1->next = node2;
Node* node3 = (Node*) malloc(sizeof(Node));
node3->data = 13;
node3->next = NULL;
node3->prev = node2;
node2->next = node3;
Node* node4 = (Node*) malloc(sizeof(Node));
node4->data = 2;
node4->next = NULL;
node4->prev = node3;
node3->next = node4;
Node* currentNode = node1;
printf("Forward: ");
while (currentNode) ,
printf("%d -> ", currentNode->data);
currentNode = currentNode->next;
printf("NULL\n");
currentNode = node4;
printf("Backward: ");
while (currentNode) ,
printf("%d -> ", currentNode->data);
currentNode = currentNode->prev;
printf("NULL\n");
free(node1);
free(node2);
free(node3);
free(node4);
return 0;
3. Circular Singly Linked List Implementation
Below is an implementation of this circular singly linked list:
#include <stdio.h>
#include <stdlib.h>
typedef struct Node ,
int data;
struct Node* next;
- Node;
int main() ,
Node* node1 = (Node*) malloc(sizeof(Node));
Node* node2 = (Node*) malloc(sizeof(Node));
Node* node3 = (Node*) malloc(sizeof(Node));
Node* node4 = (Node*) malloc(sizeof(Node));
node1->data = 3;
node2->data = 5;
node3->data = 13;
node4->data = 2;
node1->next = node2;
node2->next = node3;
node3->next = node4;
node4->next = node1; // Circular link
Node* currentNode = node1;
Node* startNode = node1;
printf("%d -> ", currentNode->data);
currentNode = currentNode->next;
while (currentNode != startNode) ,
printf("%d -> ", currentNode->data);
currentNode = currentNode->next;
-
printf("...\n"); // Indicating the list loops back
free(node1);
free(node2);
free(node3);
free(node4);
return 0;
4. Circular Doubly Linked List Implementation
Below is an implementation of this circular doubly linked list:
#include <stdio.h>
#include <stdlib.h>
typedef struct Node ,
int data;
struct Node* next;
struct Node* prev;
- Node;
int main() ,
Node* node1 = (Node*) malloc(sizeof(Node));
Node* node2 = (Node*) malloc(sizeof(Node));
Node* node3 = (Node*) malloc(sizeof(Node));
Node* node4 = (Node*) malloc(sizeof(Node));
node1->data = 3;
node2->data = 5;
node3->data = 13;
node4->data = 2;
node1->next = node2;
node1->prev = node4; // Circular link
node2->prev = node1;
node2->next = node3;
node3->prev = node2;
node3->next = node4;
node4->prev = node3;
node4->next = node1; // Circular link
printf("\nTraversing forward:\n");
Node* currentNode = node1;
Node* startNode = node1;
printf("%d -> ", currentNode->data);
currentNode = currentNode->next;
while (currentNode != startNode) ,
printf("%d -> ", currentNode->data);
currentNode = currentNode->next;
printf("...\n"); // Indicating the list loops back
printf("\nTraversing backward:\n");
currentNode = node4;
startNode = node4;
printf("%d -> ", currentNode->data);
currentNode = currentNode->prev;
while (currentNode != startNode) ,
printf("%d -> ", currentNode->data);
currentNode = currentNode->prev;
printf("...\n"); // Indicating the list loops back
free(node1);
free(node2);
free(node3);
free(node4);
return 0;
