Linked List Implementation in C++ | Techie Delight (2023)

This post provides an overview of some available techniques to implement a linked list in C++ programming language.

We know that each node of a linked list contains a single data field and a pointer to the next node in the list.

// A Linked List Node

class Node

{

public:

int key;// data field

Node* next; // pointer to the next node

};

The nodes of the linked list are allocated in the heap memory. We can use the new operator in C++ for dynamic memory allocation and the delete operator to deallocate the allocated memory.

// Utility function to return new linked list node from the heap

Node* newNode(int key)

{

// allocate the new node in a heap using the new operator and set its data

Node* node = new Node;

node->key = key;

// set the `.next` pointer of the new node to point to null

node->next = nullptr;

return node;

}

Practice this problem

There are several methods to construct a singly linked list. Each is covered in detail below:

1. Naive method

A simple solution would be to allocate memory for all individual nodes of the linked list, set their data, and rearrange their pointers to build the complete list.

2. Single Line

We can write the above code in a single line by passing the next node as an argument to the newNode() function:

#include <iostream>

using namespace std;

// A Linked List Node

class Node

{

public:

int key;// data field

Node* next; // pointer to the next node

};

// Utility function to return new linked list node from the heap

Node* newNode(int key, Node* next)

{

// allocate a new node in a heap and set its data

Node* node = new Node;

node->key = key;

// set the `.next` pointer of the new node to point to the current

// first node of the list.

node->next = next;

return node;

}

// Function for linked list implementation containing three nodes

Node* constructList()

{

Node* head = newNode(1, newNode(2, newNode(3, nullptr)));

return head;

}

// Helper function to print a linked list

void printList(Node* head)

{

Node* ptr = head;

while (ptr)

{

cout << ptr->key << " -> ";

ptr = ptr->next;

}

cout << "nullptr";

}

int main()

{

// `head` points to the first node (also known as a head node) of a linked list

Node *head = constructList();

// print linked list

printList(head);

return 0;

}

DownloadRun Code

3. Generic Method

Both above methods are not practical when the total number of nodes increases in the linked list. If the keys are given in any container, such as an array, vector, or set, we can easily construct a linked list by traversing the container, as shown below:

#include <iostream>

#include <vector>

using namespace std;

// A Linked List Node

class Node

{

public:

int key;// data field

Node* next; // pointer to the next node

};

// Utility function to return new linked list node from the heap

Node* newNode(int key, Node* next)

{

// allocate a new node in a heap and set its data

Node* node = new Node;

node->key = key;

// set the `.next` pointer of the new node to point to the current

// first node of the list.

node->next = next;

return node;

}

// Function for linked list implementation from a given set of keys

Node* constructList(vector<int> const &keys)

{

Node* head, *node = nullptr;

// start from the end of the array

for (int i = keys.size() - 1; i >= 0; i--)

{

node = newNode(keys[i], node);

head = node;

}

return head;

}

// Helper function to print a linked list

void printList(Node* head)

{

Node* ptr = head;

while (ptr)

{

cout << ptr->key << " -> ";

ptr = ptr->next;

}

cout << "nullptr";

}

int main()

{

// input keys (in reverse order)

vector<int> keys = { 4, 3, 2, 1 };

// construct linked list

Node *head = constructList(keys);

// print linked list

printList(head);

return 0;

}

4. Standard Solution

The standard solution adds a single node to the head end of any list. This function is called push() since we are adding the link to the head end, making a list look a bit like a stack.

We know that C++ has its built-in & argument feature to implement reference parameters. If we append an & to the type of parameter, the compiler will automatically make the parameter operate by reference without disturbing the argument’s type.

#include <iostream>

#include <vector>

using namespace std;

// A Linked List Node

class Node

{

public:

int key;// data field

Node* next; // pointer to the next node

};

push() in C++ — we just add `&` to the right-hand side of the head

parameter type, and the compiler makes that parameter work by reference.

So, this code changes the caller's memory, but no extra uses of `*` are

necessary — we access "head" directly, and the compiler makes that

change reference back to the caller.

void push(Node* &headRef, int key)

{

// allocate a new node in a heap and set its data

Node* node = new Node;

node->key = key;

// set the `.next` pointer of the new node to point to the current

// first node of the list.

// no extra use of `*` necessary on the head — the compiler

// takes care of it behind the scenes

node->next = headRef;

// change the head pointer to point to the new node, so it is

// now the first node in the list.

headRef = node;

}

// Function for linked list implementation from a given set of keys

Node* constructList(vector<int> const &keys)

{

Node* head = nullptr;

// start from the end of the array

for (int i = keys.size() - 1; i >= 0; i--)

{

// Note that no extra use `&` necessary — the compiler takes

// care of it here too. These calls are changing the head.

push(head, keys[i]);

}

return head;

}

// Helper function to print a linked list

void printList(Node* head)

{

Node* ptr = head;

while (ptr)

{

cout << ptr->key << " -> ";

ptr = ptr->next;

}

cout << "nullptr";

}

int main()

{

// input keys (in reverse order)

vector<int> keys = { 4, 3, 2, 1 };

// construct linked list

Node *head = constructList(keys);

// print linked list

printList(head);

return 0;

}

DownloadRun Code

5. Make head pointer global

We can construct a linked list by making the head pointer global, but this approach is not recommended since global variables are usually considered bad practice.

#include <iostream>

#include <vector>

using namespace std;

// A Linked List Node

class Node

{

public:

int key;

Node* next;

};

// Global head pointer

Node* head = nullptr;

// Takes a list and a data value, creates a new link with the given

// data and pushes it onto the list's front.

void push(int key)

{

// allocate a new node in a heap and set its data

Node* node = new Node;

node->key = key;

// set the `.next` pointer of the new node to point to the current

// head node of the list.

node->next = head;

// change the head pointer to point to the new node, so it is

// now the first node in the list.

head = node;

}

// Function for linked list implementation from a given set of keys

void constructList(vector<int> const &keys)

{

// start from the end of the array

for (int i = keys.size() - 1; i >= 0; i--) {

push(keys[i]);

}

// Helper function to print the global linked list `head`

void printList()

{

Node* ptr = head;

while (ptr)

{

cout << ptr->key << " -> ";

ptr = ptr->next;

}

cout << "nullptr";

}

int main()

{

// input keys (in reverse order)

vector<int> keys = { 4, 3, 2, 1 };

// construct linked list

constructList(keys);

// print linked list

printList();

return 0;

}

DownloadRun Code

6. Return head from the `push()` function

Another common approach many programmers follow is to return the head node from the push() function and update the head in the caller. This is demonstrated below:

Linked List Implementation in C++ | Techie Delight (2023)

1. Naive method

2. Single Line

3. Generic Method

4. Standard Solution

5. Make head pointer global

6. Return head from the push() function

6. Return head from the `push()` function