Create you own Linked-List in C++ (2023)

Linked-list is a linear data structure. Unlike lists or arrays, linked-list are stored in a not continuous location in the memory, in other words, a Linked-list is sequence of elements also called nodes, that contain the data and each node a link with the next node, and it is defined as a collection of nodes which are linked together and represents a list.

Create you own Linked-List in C++ (1)

Nodes are elements that carry data and have a connection to another node, this connection is often called pointer next. For the purposes of usage, our linked-list have nodes that can carry any built-in, derived or user-made data types and only one link or pointer to the next node. This article will teach you how to create your own linked list class in C++ with different useful methods and implementations.

Create you own Linked-List in C++ (2)

To begin, the first step of our journey is to create a class “Node” that will have two member variables: A private key that will store the data and a pointer that will link a node with other nodes (the pointer next saves the address of the next node that the first node is connected with).

Create you own Linked-List in C++ (3)

Before the class declaration, we add the pre-compiler declaration #ifndef _NODE_H #define _NODE_H #endif, with the purpose of preventing from the multiple inclusion of a same header file (you can also use #pragma once depending on the compiler you have). bellow #define _NODE_H_ we add the template<class Type> statement in order to have multiple data types in our node objects. this is our node.h header file looks like:

Create you own Linked-List in C++ (4)

The Node class have a private key which can contain data <Type> following OOP(Object Oriented Programming) paradigm of encapsulation, and a public pointer that it is initialized to NULL (nullptr for C++11) in order to avoid memory issues “Node *next{nullptr};” will be initialized to NULL. if you are not familiarize with C++11 {} is a way to initialize variables.

All the member methods are public, Node.h includes : two constructors, one with parameter data type constant reference (I recommend you to read about functions and passing by const references advantages), a default constructor, a getter and a setter for the key value and by last a destructor. Now let’s define the methods in the source file Node.cpp.

In the source file, we can find the constructor “Node::Node(const Type &data)” (the scope resolution operator “::” uses the namespace Node.h to identify and specify the content and the method belongs to that file) with a parameter value which is assigned to a member variable(key), additionally, the constructor with no parameter calls the constructor with parameter, passing a NULL value.

Create you own Linked-List in C++ (5)

The getter returns the reference of the key value and a setter that assigns the argument passed in the function (const Type &reference) to the key of the self node. Finally, a destructor that is called when the object is destroyed assigning the pointer next to nullptr in order to avoid dangling pointer.

The second step is to create the LinkedList.cpp and LinkedList.h file. In the header file LinkedList.h, we can find the member variables and methods prototypes (declarations).

The member variables are private, two Nodes pointers (Head and Tail) where the head is the first and beginning of the linked list and the tail is the last element. Both are assigned to nullptr to avoid memory issues. As an extra functionality, we will add a way to track the length (number of elements or nodes) of the linked list, a private integer that will store the number of nodes in the list initialized to 0.

Create you own Linked-List in C++ (6)

Member methods; we have 2 constructors, one with no parameter and other with a template<class Type> value, this Type data allows to add any type of the data needed to be contain in the list as I mentioned before. It should be noted that each linked list must contain the same type of data, for example, if a list is created to contain integers, its elements must be integers and no other data type can be added, we should handle this with a try and catch blocks and throwing exceptions, so that our list definition becomes more reliable for future testing.

Before getting in the list, I would like to explain the concept of traversion or iteration in the linked list. To iterate over a linked list it is required to create a temporal pointer that will be initialized to the pointer head of the list and then by de-refrencing it with the operator “->” or “(*)” (read about dereference operator), this pointer will access to the members of the head node in order to access to the *next member of the head and then be reassigned to the following node, this process is repeated until the tail or a target is reached.

Create you own Linked-List in C++ (7)

To accomplish a complete traverse of the linked list, it is common to use a while loop for linear linked list and a do-while loop for circular linked list. To begin the pointer trav(traverser) wil be initialized {this->head}, then the iteration will be performed with the statement while(trav != nullptr), then trav will be reassigned to trav = trav->next moving to the next node.

The other member methods of the class LinkedList<Type> are:

Create you own Linked-List in C++ (8)
  • append(const Type &data) adds a new node <Type data> to the end of the list (new tail). the argument can be any data type depending of the data type that the list contains o rany Node<Type>. Inside the function, the &data reference is wrapped by Node data type that we defined at the beginning of the article. The function “Node *temp<Type> = new Node<Type>{ data};” instantiates a Node to carry the value of data if referencing to (read about operator “new” ). returns a bool if the operation is successful.
Create you own Linked-List in C++ (9)
  • push(Type const &data) inserts a new node with the data passed to the beginning of the list (new head), in the same way, it wraps data into a Node and assigning this node as the new head of the list.
Create you own Linked-List in C++ (10)
  • pop() removes the last node of the list. it calls the destructor “Node::~Node()” (read about operator delete). returns a bool if the operation is successful.
  • pull() that deletes the first node of the list and calls the destructor “Node::~Node()” too. returns a bool if the operation is successful.
Create you own Linked-List in C++ (11)
  • printList() which prints out the list in order, you could print the list backwards using a stack, adding every element to the stack as it traverses the list. A good personal project would be a Smart Pointer to iterate over the list and print it.
Create you own Linked-List in C++ (12)

Additionally, a method is defined to insert a new node at a given index. This method is overloaded with two different parameters. In the same way that append() was define, inserts wraps data<Type> in a Node and then adds it onto the list in linear time.

Create you own Linked-List in C++ (13)

the method deleteAt(int index) deletes a node at a given index, if the index is more than the length of the list, it thorws 0 and stops the process.

Finally there are 4 getters to get the head, tail and a node at an index given (getHead(), getTail(), size(), and getNodeAt(int index)). These methods return the reference of the head, tail, length (number of nodes) and a node at given index.

Create you own Linked-List in C++ (16)

A related method, we are going to implement the array index operator [] overloading to our linked list, with a search time of O(n). C++ is a powerful language and many things are possible, taking advantage of this we will implement our own version of indexing in MyLinkedList<Type>. the method declaration is: “Type& operator[](const int index)” and its implementation is in the image bellow, calls getValueAtIndex(index):

Create you own Linked-List in C++ (17)

The best part of creating your own linked list is that you can add more methods and test them, learn how to play with this data structure and do exercises interview type. Finally, as a last method, the destructor must iterate over the list deleting and assigning to NULL every next pointer of each node, calling the method clear().

Create you own Linked-List in C++ (18)

In conclusion, creating your own linked list helps you to understand how this important data structure works internally and you can enjoy creating new member methods and ideas to improve your code, C++ is a complex programming language, and by doing this type of exercises you can test and improve your C++ skills and see the actual power that C++ OOP features offers(Templates, virtual functions, operator overloading, exceptions, objects relationships, dynamic casting, etc…).

Create you own Linked-List in C++ (19)

As recommendation: You should try to implement this exercises to prepare to Google, Amazon, Facebook or Apple interviews. Also, Implement a new class of smart pointers to add reliability and better memory management to your list. Use virtual functions to create interfaces and then implement them (inherit for C++) to your different types of linked list that you can create, for example, Doubly Linked List and Circular Doubly Linked List.

Thanks, this is the repository with all the code.

Top Articles
Latest Posts
Article information

Author: Msgr. Refugio Daniel

Last Updated: 03/17/2023

Views: 6485

Rating: 4.3 / 5 (74 voted)

Reviews: 81% of readers found this page helpful

Author information

Name: Msgr. Refugio Daniel

Birthday: 1999-09-15

Address: 8416 Beatty Center, Derekfort, VA 72092-0500

Phone: +6838967160603

Job: Mining Executive

Hobby: Woodworking, Knitting, Fishing, Coffee roasting, Kayaking, Horseback riding, Kite flying

Introduction: My name is Msgr. Refugio Daniel, I am a fine, precious, encouraging, calm, glamorous, vivacious, friendly person who loves writing and wants to share my knowledge and understanding with you.