A Complete Guide to Linked Lists In C++

Filed Under: C++
LinkedListInC

In this article, we are going to discuss Linked Lists and learn to implement a Linked List in C++.

What is a Linked List in C++?

A linked list is a container that usually consists of two members – a data element and a pointer element. Linked lists are non-contiguous data structures. Unlike arrays, random elements are not accessible in linked lists. Linked lists are broadly classified into two major types namely forward and doubly-linked lists.

Both the categories have their own advantages and disadvantages. Singly-linked lists consume less memory while doubly linked lists require more memory. Similarly, single-linked lists are less time-efficient while doubly-linked lists are much more time optimized as compared to singly-linked lists.

Where do we need Linked Lists?

We use forward linked lists in the following real-life applications,

  • Implementing stack, heaps and queues
  • Representing sparse arrays
  • Implemetation of graphs
  • Dynamic memory allocation
  • Performing arithmetic operations on long integers
  • Image viewers
  • Music players

Visualizing a Linked List

As discussed earlier, a linked list consists of a data element and a pointer pointing to the subsequent element of the linked list. Below is a diagram showing how does a linked list look like

LinkedList
LinkedList

Let’s implement a linked list in C++

We will implement a C++ program that will be having a linked list class and implement a function to print a linked list.

1. Basic structure of an element of a linked list

class Node
{
public:
	int data;
	Node* next;
	Node(int data);
};

Node::Node(const int data): data(data) next(NULL) {}

2. Implementing the insert function

  • In this function we will first check if the head is empty or not
  • If the head of the linked list is already empty, we will create a new node and initialize it with the value provided to the insert function
  • If the head is already pointing to some element, we will follow a different approach
    • We will create a new Node element and initialize it with the data provided
    • Then make the head of newly created node to point to the node, which is currently being pointed by the head of the linked list
    • The final step is to make the head of the linked list point to the newly created Node
    • By following this approach we assure that no data is lost during the process
void print_linked_list(const Node* head)
{
	//check if the head contains some data or not
	if(head == NULL)
		return;
	
	cout << endl << "Head is: ";
	while(head != NULL)
	{
		cout << head->data<< "-->" << " ";
		head = head->next;
	}
	cout << "Null" << endl << endl;
}

Complete C++ Code for Linked Lists

#include <iostream>

using namespace std;

//Node class: this class defines the structure
//of a single node of a linked list
class Node
{
public:

	//Data members of the node class
	int data;
	Node* next;

	//Default constructor prototype of an object of type node
	Node(int data);
};

//Default constructor of the node class definition
Node::Node(const int data): data(data) next(NULL) {}

//Function to insert the data at the head of the linked list
//Notice that the head of the linked list is passed by reference
//to avoid data copying(wastage of time and memory)
void insert_at_head(Node* &head, int data)
{
	if(head == NULL)
	{
		head = new Node(data);
		return;
	}

	Node*temp = new Node(data);
	temp->next = head;
	head = temp;

	return;
}

//Function to print the linked list
//Notice that the head of the of the linked list is passed at a constant
//This prevents the actual data of the linked list
//from getting modified during this function call
void print_linked_list(const Node* head)
{
	//check if the head contains some data or not
	if(head == NULL)
		return;
	
	cout << endl << "Head is: ";
	while(head != NULL)
	{
		cout << head->data<< "-->" << " ";
		head = head->next;
	}
	cout << "Null" << endl << endl;
}

int main()
{
	//Creating the head of the linked list
	//Be careful while working with pointers
	//Don't forget to initialize the value of a pointer
	//when it is create, otherwise you might end up
	//running into a segmentation fault
	Node* head = NULL;
	cout << "Enter elements(Enter -1 to stop)" << endl;

	//Taking the input
	while(true)
	{
		int ele;
		cin >> ele;

		if(ele == -1)
			break;

		insert_at_head(head, ele);
		print_linked_list(head);
	}

	return 0;
}

Linked List Program
Linked List Program

Output

Linked List Program Output
Linked List Program Output

Conclusion

In this article, we learned about the structure of a linked list. By the means of code, we further looked at the implementation of a linked list in a C++ program. We implemented three basic features of a linked list namely, structure, insert function, and print function.

References

To learn more about linked lists, you can refer to the following websites,

http://www.cplusplus.com/articles/LACRko23/

https://en.cppreference.com/w/cpp/container/list

close
Generic selectors
Exact matches only
Search in title
Search in content