C++ Tutorial: Intro to Linked Lists

June 13th, 2014

In this tutorial, we will be looking at linked lists in C++. The code at the bottom of this page has everything you need to create a working linked list example. (You can also download the program files you need from the Github link here). To make it fun, I decided to make it applicable to daily life. Almost everyone likes music, so the linked list in this tutorial will represent a song playlist.

What is a Linked List?

Basically, a linked list is a data structure that can store an indefinite amount of items. These items don’t have to be the same data type. As long as pointers connect these items in a sequential manner, it technically counts as a linked list.

Linked_List_0

Arrays vs. Linked Lists

Usually, programmers learn about arrays before they learn about linked lists, so it’s useful to compare the two. Although arrays and linked lists are both data structures for storing multiple values, there are some major differences between the two. There are pros and cons to using each.

Array Linked Lists
  • Physically Contiguous
  • Fixed Length
  • Access Elements by Index
  • Insertion/Removal is Costly
  • Logically Contiguous Only
  • Changeable Length
  • Access Elements by Traversal
  • Insertion/Removal is Efficient

    Memory Allocation

    Unlike a linked list, an array is both physically and logically contiguous. A good way to think about an array is to imagine a single chunk of memory cells. The elements of an array are actually located next to each other as consecutive memory addresses in RAM (Random Access Memory).

    array_memory_1

    The elements of a linked list, by contrast, are logically contiguous in their implementation, but not physically contiguous in memory. A linked list doesn’t occupy a single block of memory, allowing it to use whatever memory “scraps” are available. Because of this flexibility, node elements can be different sizes as well as different data types.

    heap_1

    Length

    Perhaps the most obvious difference between a linked list and an array is the fact that an array is a fixed length while a linked list can expand or shrink during runtime. Memory slots can be added or removed from a linked list as needed. In an array, however, you are stuck with an inflexible chunk of memory cells for the array’s lifetime. Even a dynamic array (one that is assigned a length during runtime) is incapable of changing length once it’s created.

    Accessing Elements

    One advantage an array has over a linked list is indexing. Instead of having to traverse down every element in the array, you can access an element directly by its index number. This costs only one instruction cycle. To get the fifth element of an array, you only need to perform one lookup operation. The same operation in a linked list would cost you five instruction cycles since you have to “inchworm” your way down the list.

    In technical terms, retrieving an element by its index number in an array is always an O(1) operation. By contrast, the same logically-equivalent operation in a linked list would take a variable amount of runtime depending on the number of elements preceding the one you’re trying to access. Thus, retrieving a particular element in a linked list would be an O(n) operation at worst and an O(1) operation at best (if the sought-after element happens to be at the front of the list).

    Inserting/Removing Elements

    One advantage a linked list has over an array is the ease of inserting and removing elements. In order to insert an element into the middle of an array, you have to shift each element over to make space for insertion. This can be quite costly. In a linked list, however all you need to do is reassign the pointer of one node to make it point to the new element and have that new element point to the next logical node in the sequence.

    Types of Linked Lists

    There are several kinds of linked lists. In a singly linked list, each node has only one pointer, commonly called “next” since it points to the next node in the sequence. The first node is called the “head” of the list. The last node in the list points to NULL.

    Linked_List_2 copy

    A singly linked list can become a circular node by assigning the address of the head node to the tail node instead of NULL. This isn’t a particularly useful linked list, but it illustrates the flexibility of this data structure.

    Linked_List_4 copy

    A doubly linked list has two pointer variables, one pointing forward to the next node and one pointing back to the previous node. In this tutorial, we will create a program for a singly linked list since it’s the simplest kind of list. We will use the list to represent a music playlist where each node represents a song and artist combination.

    Linked_List_3 copy

    Linked List Nodes

    The elements of a linked list are usually referred to as “nodes.” A C++ linked list is composed of node structs, each with a data component and a pointer to other nodes in the list. The data attributes of the node in this example store a song name and an artist name. The next pointer refers to the next song in the playlist.

    Node

    Designing the Class

    As a budding programmer, I was eager to bypass the high-level design phase and get to coding right away. With experience, however, I learned that taking the time to design the program components on paper first made a huge difference. It has saved me a lot of time and frustration. For object-oriented programming in particular, it’s a good idea to use UML (Universal Modeling Language) diagrams for representing classes.

    Below is a UML diagram for the LinkedList class design. It’s a collection of fairly basic linked list operations and data attributes.

    LinkedList
    Attributes:
    • head: node reference
    • listLength: integer
    Behaviors:
    • LinkedList(): constructor
    • insertNode(): boolean
    • removeNode(): boolean
    • printList(): void
    • ~LinkedList(): destructor

    You can download the program files you need from the Github link here.

    LinkedList.h

    Copy and paste the code below into your LinkedList header file. This is the next step after designing the LinkedList class in the UML diagram.

    //*******************************************************************
    //  LinkedList.h
    //  LinkedList_Project
    //
    //  Created by Karlina Beringer on June 12, 2014.
    //  This header file contains the LinkedList class declarations.
    //*******************************************************************
    
    #ifndef LinkedList_h
    #define LinkedList_h
    
    #include <iostream>
    #include <string>
    using namespace std;
    
    //*******************************************************************
    // Node structs contain data and a pointer to the next node.
    // In this project, it will represent a song/artist combination.
    //*******************************************************************
    struct node
    {
        string song;
        string artist;
        node * next;
    };
    
    //*******************************************************************
    // LinkedList is a list of singly-linked nodes.
    // In this project, it will represent a song playlist.
    //*******************************************************************
    class LinkedList
    {
    private:
        // Head of the list contains no song data, 
        // but points to the song playlist.
        node * head;
        int listLength;
        
    public:
        // Default Constructor creates the head node.
        LinkedList();
        
        // Setter adds a node to the list at a given position.
        // Takes a node and list position as parameters.
        // Position must be between 1 and the number of data nodes.
        // Returns true if the operation is successful.
        bool insertNode( node * newNode, int position );
        
        // Setter removes a node by its given position.
        // Returns true if the operation is successful.
        bool removeNode( int position );
    
        // Prints each node in the list in consecutive order,
        // starting at the head and ending at the tail.
        // Prints list data to the console.
        void printList();
        
        // Destructor de-allocates memory used by the list.
        ~LinkedList();
    };
    
    #endif
    

    LinkedList.cpp

    Copy and paste the code below into your Linked List source file. This is where we flesh out the methods of the LinkedList class.

    //*******************************************************************
    //  LinkedList.cpp
    //  LinkedList_Project
    //
    //  Created by Karlina Beringer on June 12, 2014.
    //  This source file contains the LinkedList class definitions.
    //*******************************************************************
    
    #include "LinkedList.h"
    
    // Default Constructor creates the head node.
    LinkedList::LinkedList()
    {
        head -> song = "head (contains no song data)";
        head -> artist = "head (contains no artist data)";
        head -> next = NULL;
        listLength = 0;
    }
    
    // Setter adds a node to the list at a given position.
    // Takes a node and list position as parameters.
    // Position must be between 1 and the number of data nodes.
    // Returns true if the operation is successful.
    bool LinkedList::insertNode( node * newNode, int position )
    {
        if ((position <= 0) || (position > listLength + 1))
        {
            cout << "nError: the given position is out of range.n";
            return false;
        }
        if (head -> next == NULL) 
        {
            head -> next = newNode;
            listLength++;
            return true;
        } 
        int count = 0;
        node * p = head;
        node * q = head;
        while (q)
        { 
            if (count == position)
            {
                p -> next = newNode;
                newNode -> next = q;
                length++;
                return true;
            }
            p = q;
            q = p -> next;
            count++;
        }
        if (count == position)
        {
            p -> next = newNode;
            newNode -> next = q;
            listLength++;
            return true;
        }
        cout << "nError: node was not added to list.n";
        return false;
    }
    
    // Setter removes a node by its given position.
    // Returns true if the operation is successful.
    bool LinkedList::removeNode( int position )
    {
        if ((position <= 0) || (position > listLength + 1))
        {
            cout << "nError: the given position is out of range.n";
            return false;
        }
        if (head -> next == NULL)
        {
           cout << "nError: there is nothing to remove.n";
           return false;
        }
        int count = 0;
        node * p = head;
        node * q = head;
        while (q) 
        {
            if (count == position)
            {
                p -> next = q -> next;
                delete q;
                listLength--;
                return true;
            }
            p = q;
            q = p -> next;
            count++;
        }
        cout << "nError: nothing was removed from the list.n";
        return false;
    }
    
    // Prints each node in the list in consecutive order,
    // starting at the head and ending at the tail.
    // Prints the data to the console.
    void LinkedList::printList()
    {
        node * p = head;
        node * q = head;
        cout << "n---------------------------n";
        cout << "Song Playlist n";
        while (q)
        {
            p = q;
            cout << "n-----------------------------n";
            cout << "t position: " << count << endl;
            cout << "t song: " << p -> song << endl;
            cout << "t artist: " << p -> artist << endl;
            q = p -> next;
            count++;
        }
    }
    
    // Destructor de-allocates memory used by the list.
    LinkedList::~LinkedList() 
    {
        node * p = head;
        node * q = head;
        while (q)
        {
            p = q;
            q = p -> next;
            if (q) delete p;
        }
    }

    main.cpp

    Finally, copy and paste the code below into your driver source file. This is where we see the LinkedList class in action. The code below will generate some song nodes and add, remove, and display them as in a playlist.

    //*******************************************************************
    //  main.cpp
    //  LinkedList_Project
    //
    //  Created by Karlina Beringer on June 12, 2014.
    //  This driver implements the LinkedList class.
    //*******************************************************************
    
    #include "LinkedList.h"
    using namespace std;
    
    int main()
    {
        // STEP 1: Create some unlinked song nodes.
        node * A = new node;
        A -> song = "We Are";
        A -> artist = "Vertical Horizon";
        
        node * B = new node;
        B -> song = "I Stand Alone";
        B -> artist = "Godsmack";
        
        node * C = new node;
        C -> song = "Heir Apparent";
        C -> artist = "Opeth";
        
        node * D = new node;
        D -> song = "Fear of the Dark";
        D -> artist = "Iron Maiden";
        
        node * E = new node;
        E -> song = "Blue Monday";
        E -> artist = "New Order";
        
        node * F = new node;
        F -> song = "The Moth";
        F -> artist = "Aimee Mann";
        
        // STEP 2: Build a list of three song nodes by appending to end of list.
        LinkedList myList;
        myList.insertNode(A, 1);
        myList.insertNode(B, 2);
        myList.insertNode(C, 3);
        myList.insertNode(D, 4);
        myList.printList();
        
        // STEP 3: Insert a node into middle of list.
        myList.insertNode(E, 2);
        myList.printList();
        
        // STEP 4: Insert node at the front of list.
        myList.insertNode(F,1);
        myList.printList();
        
        // STEP 5: Remove the last node from the list.
        myList.removeNode(6);
        myList.printList();
        
        // STEP 6: Remove the first node from the list.
        myList.removeNode(1);
        myList.printList();
        
        // STEP 7: Remove a node from the middle of the list.
        myList.removeNode(3);
        myList.printList();
        
        return 0;
    }
    

    References:

    1. Brain, Marshall. “Pointers: Understanding Memory Addresses.” How Stuff Works, Inc. 2014. http://computer.howstuffworks.com/c23.htm
    2. “Linked Lists.” cplusplus.com. 12 October 2011. http://www.cplusplus.com/articles/Lw6AC542/
    3. Malik, D. S. C Programming: From Problem Analysis to Program Design. Boston, MA: Course Technology, 2009. Print.

Categories: mathtechnologytutorials