What is a linked list

A common concept taught when learning data structures is a topic called the Linked List. What a Linked List does is that they are used to store data with structures, which allow programmers to create a new place to store data when needed. The data is set of records linked together by references, which are called nodes. The references are known as pointers. The pointers in a Linked List are only dereferenced or compared by equality, thus linked data structures require the task of adding and subtracting pointers.

An analogy to clarify an understanding of pointers is to think of it like several train carriages connected together. The train would store the first train carriage in front, then use connectors to attach several train carriages. Each time a new train carriage is added, it uses a connector to add a new train carriage. The pointer would be the connector between the train carriages. This like like a programming using the new keyword to create a pointer to a new struct or class.

Diagram explaining that each node points to another node

linkedlist diagram

Applying the linkedlist data structure concept in C++

#include <iostream>

using namespace std;

//−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−
// LinkedList Class
//−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−
class LinkedList 
{
 struct Node
 {
 int x;
 Node *next;
 };

public:
 LinkedList(); // Constructor
 ~LinkedList(); // Destructor
 void addValue(int val);
 int popValue();

private:
 Node *head; // Pointer to the first node

};

//−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−
// Implementing a linked list constructor
//−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−
LinkedList::LinkedList()
{
 head = NULL;
}

LinkedList::~LinkedList()
{
 cout << "Allocated Memory values will be deleted\n";
}

void LinkedList::addValue(int val)
{

 Node *n = new Node(); // Creates a new node
 n−>x = val; // Set value
 n−>next = head; // Make the node point to the next node in the list

 head = n;
}

int LinkedList::popValue()
{
 Node *n = head;
 int ret = n−>x;

 head = head−>next;
 delete n;
 return ret;
}

int main()
{
 // Create the class object
 LinkedList list;

 // Add values
 list.addValue(10);
 list.addValue(20);
 list.addValue(50);

 cout << list.popValue() << "\n";
 cout << list.popValue() << "\n";
 cout << list.popValue() << "\n";

 return 0;
}
Share this post