Linked List Tutorial - Singly, Doubly, and C++ Code

Introduction - What Are Linked Lists?

Arrays and Linked Lists are the two fundamental types of data structures in programming, and every other advanced data structure is some form of array or linked list (or at least borrow the concept). An array is a contiguous block of memory reserved for holding data, but linked lists contain one data point, and have a pointer to another place in memory for the next data point.

An array holds all of the data in one block in memory, but a linked list has individual datapoints anywhere in memory.

Why Use A Linked List Instead Of An Array?

So why use a Linked List instead of an array? Let's go through some reasons.

Why Linked Lists Are Good:

1. Linked Lists allow for very efficient use of memory if you don't know how much data you'll be adding to it (or if you ever need to add/remove data points afterward).
2. An array's size has to be declared when initializing it. A linked list has no initialization requirements. (Resizable arrays (such as lists and vectors) require extra time and memory to continuously resize themselves.)

Why Linked Lists Are Bad (And Why Arrays Are Good):

1. Sorting arrays are MUCH easier than sorting linked lists. 
2. Looking up a value in an array is much quicker than finding a value in a linked list. (You can look up the exact spot in memory to find your data, which is O(1), as opposed to a linked list, where you have to follow the pointers through the list, which is O(N).)

Singly And Doubly Linked Lists

There are two types of linked lists (sort of).

A singly linked list has a single pointer from one data point to the next data point in the list. 

A singly linked list example.

A doubly linked list contains not only a pointer to the next data point, but also contains a pointer to the previous data point.

A doubly linked list example.

Linked List C++ Code (Creation and Traversal)

Here's some code to show how Linked Lists work in C++.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122

// Copyright srcmake.com 2018. // C++ Linked List (Singly and Doubly) Examples // Official webpage for this tutorial: https://www.srcmake.com/home/linkedlist /* Compile with: g++ -std=c++14 main.cpp -o run ./run */ #include <iostream> using namespace std; ////////////////////////////////////////////////////// ////// LINKED LIST NODES ////// // A singly node. struct singlyNode { int data; singlyNode* next; }; // A doubly node. struct doublyNode { int data; // The data we're storing. doublyNode* next; // The next node in the list. doublyNode* prev; // The previous node in the list. }; ////////////////////////////////////////////////////// ////////////////////////////////////////////////////// ////// ADD NODE TO LIST ////// // Add a node to the end of a doubly linked list. // Pass a reference to a pointer to the root node, and the data. void AddNode(doublyNode*& root, int data) { // Special case: if the root is null, then since this is the first node, make root point to it. if(root == NULL) { //cout << "root"; // Create a new node, and set it's next and prev pointers to null, and set the data. doublyNode* nodePtr = new doublyNode(); nodePtr->next = NULL; nodePtr->prev = NULL; nodePtr->data = data; // Now make the root pointer that we were passed point to the address of this new node. root = nodePtr; } // Normal case: Go to the end of the list, create a new node for the data, and add it to the end of the list. else { // Create a new node for the data we're trying to add. doublyNode* newnode = new doublyNode(); newnode->next = NULL; newnode->data = data; // Find the node at the end of the list. // Create a pointer that starts out pointing to the root node. doublyNode* nodePtr = root; // Keep going down the list until we find the last node. while(nodePtr->next != NULL) { // Set the node to the next one in the list. nodePtr = nodePtr->next; } // node is now pointing to the node at the end of the last. // Make the newnode's prev pointer point to the address of the last node. newnode->prev = nodePtr; // Make the last node's next address point to the address of the new node. nodePtr->next = newnode; } } ////////////////////////////////////////////////////// ////////////////////////////////////////////////////// ////// PRINT NODES ////// // Print all nodes in the list. Recursively print the node's data and move to the next node. void PrintLinkedList(doublyNode* nodePtr) { // If this node is null, stop. if(nodePtr == NULL) { cout << endl; return; } // Print this node's data. cout << nodePtr->data << " "; // Recursively check the next node in the list. PrintLinkedList(nodePtr->next); } ////////////////////////////////////////////////////// ////////////////////////////////////////////////////// ////// MAIN ////// int main() { cout << "Program started.\n"; // Our linked list will be 4 6 1 -5. // Create a pointer for the root of our linked list. Set it to point to nothing. doublyNode* root = NULL; // Add the nodes we want to our linked list. AddNode(root, 4); AddNode(root, 6); AddNode(root, 1); AddNode(root, -5); // Print the list (by traversing it in order). Pass it the root pointer. cout << "\nPrinting Linked List: "; PrintLinkedList(root); cout << "Program ended.\n"; return 0; } //////////////////////////////////////////////////////

The hardest thing about the code is keeping track of the pointers. Remember, create a new node with the new keyword. We need the node to show up on the heap. 

Conclusion

Linked Lists are often overlooked in favor of arrays, stacks, queues, etc., but they're fundamental to understand and very popular in interview questions.

We'll look at some popular linked list questions in future blog posts.

​Like this content and want more? Feel free to look around and find another blog post that interests you. You can also contact me through one of the various social media channels. 

Twitter: @srcmake
Discord: srcmake#3644
Youtube: srcmake
Twitch: www.twitch.tv/srcmake
​Github: srcmake