how to create a linked list c++

TL;DR – A linked list in C++ is a form of data structure. It stores data that is connected by pointers in a consistent pattern.

1. What is a Linked List in C++?
2. Linked List Implementation
3. Creating C++ Linked List
4. Linked List Manipulation
5. Insertion
5.1. Inserting at the Start
5.2. Inserting at the End
5.3. Inserting at a Specific Position
6. Linked List C++: Useful Tips

What is a Linked List in C++?

There are two types of linked lists: a singly-linked list and a doubly-linked list.

The singly-linked list contains nodes that only point to the next node. The C++ doubly linked list has nodes that can point towards both the next and the previous node.

A node has two parts: the data part and the next part. The data part contains the stored data, and the next part provides the address of the next node.

The first node of a linked list is called the head, and the last node is called the tail. The list starts traversing from the head, while the tail ends the list by pointing at NULL.

Linked List C++

Linked List Implementation

Let's create a structure for a single node first. Since a node consists of the data part and the next part, here is how the structure looks:

Example

                                                struct                  Node                  {                int                data;                                  struct                  Node                  *next;                };

As you can see, the struct node comprises of two parts: the int data which represents the data part that holds the integer value, and the node next which represents a node pointer called next.

Creating C++ Linked List

To create a linked list, you have to launch a class. It will include the functions that control the nodes:

Example

                              #include                  <bits/stdc++.h>                                using                namespace                std;                                  int                  main                  ()                {                                  class                  Node                  {                public:                int                data;         Node * next;     }; }

Let's create three nodes in sequence. Make sure that each node is pointing to NULL at first since the pointers will be added later as you input the data.

Example

                              #include                  <cstddef>                                using                namespace                std;                                  class                  Node                  {                public:                int                data;     Node * next; };                                  int                  main                  ()                {     Node * head =                NULL;     Node * second =                NULL;     Node * third =                NULL;      head =                new                Node();     second =                new                Node();     third =                new                Node(); }

Next, let's put data values and pointers into each node. Each node, except the third one, should point to the subsequent nodes. The third node's tail should point to NULL.

Example

                              #include                  <cstddef>                                using                namespace                std;                                  class                  Node                  {                public:                int                data;     Node * next; };                                  int                  main                  ()                {     Node * head =                NULL;     Node * second =                NULL;     Node * third =                NULL;      head =                new                Node();     second =                new                Node();     third =                new                Node();      head->data =                1;     head->next = second;      second-> data =                2;     second-> next = third;      third-> data =                3;     third-> next =                NULL; }

After filling out the data part and the next part in each node, the linked list is now complete. You can start to traverse the list starting from the head.

Linked List Manipulation

After creating a fully functioning linked list, you might want to see its output. Hence, you can display it by printing the values of the nodes.

Basically, you should create a temporary node and point it to the head. Then the pointers will continue until all the values of the nodes are printed:

Example

                              #include                  <cstddef>                                #include                  <iostream>                                using                namespace                std;                                  class                  Node                  {                public:                int                data;     Node * next; };                                  void                  print_list                  (Node * n)                {                while                (n !=                NULL) {                cout                << n->data <<                " ";         n = n->next;     } }                                  int                  main                  ()                {     Node * head =                NULL;     Node * second =                NULL;     Node * third =                NULL;      head =                new                Node();     second =                new                Node();     third =                new                Node();      head->data =                1;     head->next = second;      second->data =                2;     second->next = third;      third->data =                3;     third->next =                NULL;      print_list(head); }

Pros

Simplistic design (no unnecessary information)
High-quality courses (even the free ones)
Variety of features

Main Features

Nanodegree programs
Suitable for enterprises
Paid certificates of completion

Pros

Easy to navigate
No technical issues
Seems to care about its users

Main Features

Huge variety of courses
30-day refund policy
Free certificates of completion

Pros

Great user experience
Offers quality content
Very transparent with their pricing

Main Features

Free certificates of completion
Focused on data science skills
Flexible learning timetable

Insertion

Aside from displaying the list's output, you can also manipulate it by inserting new nodes into the list. It's pretty easy, and there are three ways you can choose.

Inserting at the Start

Inserting a new node at the start of the list means that the new node will serve as the new head. Since it will push the former head aside, the process uses the push() function.

Example

                              #include                  <cstddef>                                #include                  <iostream>                                using                namespace                std;                                  class                  Node                  {                public:                int                data;     Node * next; };                                  void                  print_list                  (Node * n)                {                cout                <<                "\nPrinting new list..."                <<                endl;                while                (n !=                NULL) {                cout                << n->data <<                " ";         n = n->next;     } }                                  void                  push                  (struct Node ** head_ref,                    int                    new_data)                {                                  struct                  Node                  *                  new_node                  = (struct                  Node                  * )                  malloc(sizeof(struct                  Node));                new_node->data = new_data;     new_node->next = ( * head_ref);     ( * head_ref) = new_node; }                                  int                  main                  ()                {     Node * head =                NULL;     Node * second =                NULL;     Node * third =                NULL;      head =                new                Node();     second =                new                Node();     third =                new                Node();      head->data =                1;     head->next = second;      second->data =                2;     second->next = third;      third->data =                3;     third->next =                NULL;      print_list(head);     push(&head,                11);     print_list(head); }

As you can see in the code, it inserts the new node as the head. It also fills the data within the node. Moreover, it adjusts the pointer to start from the new head.

Inserting at the End

If you add a new node at the end of the list, it'll become the end of the traversal within the list. In other words, you should set the new node to point at NULL.

Example

                              #include                  <cstddef>                                #include                  <iostream>                                using                namespace                std;                                  class                  Node                  {                public:                int                data;     Node * next; };                                  void                  print_list                  (Node * n)                {                cout                <<                "\nPrinting new list..."                <<                endl;                while                (n !=                NULL) {                cout                << n->data <<                " ";         n = n->next;     } }                                  void                  append                  (struct Node ** head_ref,                    int                    new_data)                {                                  struct                  Node                  *                  new_node                  = (struct                  Node                  * )                  malloc(sizeof(struct                  Node));                                  struct                  Node                  *                  last                  = *                  head_ref;                new_node->data = new_data;     new_node->next =                NULL;                while                (last->next !=                NULL)         last = last->next;     last->next = new_node; }                                  int                  main                  ()                {     Node * head =                NULL;     Node * second =                NULL;     Node * third =                NULL;      head =                new                Node();     second =                new                Node();     third =                new                Node();      head->data =                1;     head->next = second;      second->data =                2;     second->next = third;      third->data =                3;     third->next =                NULL;      print_list(head);     append(&head,                11);     print_list(head); }

Aside from adjusting the pointer of the new node, don't forget to fill in the data. You should also set the former tail to point to the new node since it becomes the new tail.

Inserting at a Specific Position

The purpose of this method is to put a new node between the head and the tail. You have to fill the data and adjust the pointer of the new node with its previous node.

Example

                              #include                  <cstddef>                                #include                  <iostream>                                using                namespace                std;                                  class                  Node                  {                public:                int                data;     Node * next; };                                  void                  print_list                  (Node * n)                {                cout                <<                "\nPrinting new list..."                <<                endl;                while                (n !=                NULL) {                cout                << n->data <<                " ";         n = n->next;     } }                                  void                  insertAfter                  (struct Node * prev_node,                    int                    new_data)                {                if                (prev_node ==                NULL) {                printf("the given previous node cannot be NULL");                return;     }                                  struct                  Node                  *                  new_node                  = (struct                  Node                  * )                  malloc(sizeof(struct                  Node));                new_node->data = new_data;     new_node->next = prev_node->next;     prev_node->next = new_node; }                                  int                  main                  ()                {     Node * head =                NULL;     Node * second =                NULL;     Node * third =                NULL;      head =                new                Node();     second =                new                Node();     third =                new                Node();      head->data =                1;     head->next = second;      second->data =                2;     second->next = third;      third->data =                3;     third->next =                NULL;      print_list(head);     insertAfter(second,                11);     print_list(head); }

The pointer of the new node and the previous node swap, which means the previous node will point to the new node, whereas the new node will point to the next node. That way, the traversal process will run on the right track.

Linked List C++: Useful Tips

When forming a linked list, make sure all the nodes are connected.
You start creating a linked list by filling data in each node to set pointers between the nodes.