• Insertion at the top of the listing.
• Insertion at the bottom of the page.

So, while developing your code to create Linked List, we will include ways to add additional data items to the linked list both at the start of the list and at the end.

We will also add additional valuable techniques, such as:

• Examining whether the Linked List is empty or not.
• Finding an element of data in the Linked List
• The removal of a specific Node(data element) from the List

Before we learn how to add data to linked lists, we need to understand the elements that make up linked lists. the primary element will be known as the Node.

What is a Node?

A Node in linked lists contains the value of data and the pointer, which indicates the exact location of the next Node of the linked list.

In the above image, there is an linked list that contains four nodes. Each Node includes specific data(A B, C, and D) and a pointer, which is used to store the exact location for the Node next to it.

You might be wondering why we should keep track of the whereabouts of the Node next to us. Because the memory locations assigned to these nodes do not appear to be connected, each Node must be aware of the location where the next Node’s data is in memory.

The Node is a collection of many data; we’ll define an appropriate class for Node that will include an array of variables to keep the information as well as a variable that stores information about the reference. We do this in C, the language we build structures by using the structure keyword.

class Node 
{
    public:
    // our linked list will only hold int data
    int data;
    //pointer to the next node
    node* next;
  
    // default constructor
    Node() 
    {
        data = 0;
        next = NULL;
    }
    
    // parameterised constructor
    Node(int x) 
    {
        data = x;
        next = NULL;
    }
} 

You can also set the Node property data for the class and data next private, but in that the case, we’ll have to include the setter and getter methods for accessing them(don’t know what the getter and setter methods are called: functions inline within C++ ). It is possible to add the getter and setter function to the class Node in the following way: class as follows:

class Node 
{
    // our linked list will only hold int data
    int data;
    //pointer to the next node
    node* next;
  
    // default constructor same as above
    
    // parameterised constructor same as above
    
    /* getters and setters */
    // get the value of data
    int getData() 
    {
        return data;
    }

    // to set the value for data
    void setData(int x) 
    {
        this.data = x;
    }
    // get the value of next pointer
    node* getNext() 
    {
        return next;
    }
    // to set the value for pointer
    void setNext(node *n) 
    {
        this.next = n;
    }
}

Node class creates a Node to store the information to be added to the Linked List. When the object of this class Node is constructed. We can use various methods to integrate the Node in the Linked List.

Linear Linked List class

Since we follow the entire OOPS approach, we’ll create a distinct class called linked lists, and it will contain every method, like the insertion or deletion, search or search. In addition, this class will include the capability of a pointer known as Head to keep track of the exact location of the first Node that will add to the linked list.

class LinkedList 
{
    public:
    node *head;
    //declaring the functions
  
    //function to add Node at front
    int addAtFront(node *n);
    //function to check whether Linked list is empty
    int isEmpty();
    //function to add Node at the End of list
    int addAtEnd(node *n);
    //function to search a value
    node* search(int k);
    //function to delete any Node
    node* deleteNode(int x);
  
    LinkedList() 
    {
        head = NULL;
    }
}

Insertion at the Beginning

How to inserting the Node at the beginning of the process :

1. 1. The initial Node will be the Head of every Linked List.
2. If a new Linked List is instantiated, it will only have one Head. This Head is null.
3. In addition, the Head holds the pointer to the initial Node of the List.
4. When we want to include any Node in the front of the Node, it is necessary to create a headpoint.
5. The next pointer, which is the new Node, should be pointing to the Head before it. Regardless of whether it is NULL(in the case of an entirely new List). The reference to the initial Node on the List.
6. The prior head Node will now be the second Node of Linked List because it is now the second Node is put in front of the existing.

int LinkedList :: addAtFront(node *n) {
  int i = 0;
  //making the next of the new Node point to Head
  n->next = head;
  //making the new Node as Head
  head = n;
  i++;
  //returning the position where Node is added
  return i;
}

Inserting at the End

How to add steps to insert a Node at the end:

1. When you find that the Linked List is empty, we include the newly created Node to the Linked List head.
2. If the Linked List is not empty, we will find the last Node, place it in the new Node. Make the new Node the final Node.

int LinkedList :: addAtEnd(node *n) {
  //If list is empty
  if(head == NULL) {
    //making the new Node as Head
    head = n;
    //making the next pointe of the new Node as Null
    n->next = NULL;
  }
  else {
    //getting the last node
    node *n2 = getLastNode();
    n2->next = n;
  } 
}

node* LinkedList :: getLastNode() {
  //creating a pointer pointing to Head
  node* ptr = head;
  //Iterating over the list till the node whose Next pointer points to null
  //Return that node, because that will be the last node.
  while(ptr->next!=NULL) {
    //if Next is not Null, take the pointer one step forward
    ptr = ptr->next;
  }
  return ptr;
}

Searching for an Element in the List

In the process of searching, we don’t need to perform a lot. It is just a matter of having to navigate the same way we did in the case of the previous Node. In this instance, we’ll examine the information from the Node. If we find the Node with the same information. The Node will be returned or, if not, we will assign our pointer points the next Node and so on.

node* LinkedList :: search(int x) {
  node *ptr = head;
  while(ptr != NULL && ptr->data != x) {
    //until we reach the end or we find a Node with data x, we keep moving
    ptr = ptr->next;
  }
  return ptr;
}

Deleting a Node from the Linear Linked List

A node’s deletion can be accomplished in various ways, such as the first lookup of the Node using information that we would like to erase and finally erase it. Our method creates a procedure that will use data to be deleted as an argument, take the data to be deleted as an argument, and then use an algorithm to find the data and then delete this Node’s entry from our list.

To remove a Node in the directory, we have to follow these steps :

• If you are sure that the Node to be deleted is the primary Node. Set the Next pointer in the Head at the next element in the Node to be removed.
• In the event that the Node is located in the middle, look for the Node before it. Then make the Node before it points at the Node adjacent to it.

node* LinkedList :: deleteNode(int x) {
  //searching the Node with data x
  node *n = search(x);
  node *ptr = head;
  if(ptr == n) {
    ptr->next = n->next;
    return n;
  }
  else {
    while(ptr->next != n) {
      ptr = ptr->next;
    }
    ptr->next = n->next;
    return n;
  }
}

Checking whether the List is empty or not

We only need to verify for it is true that the Head of the list has been set to Null and if it is not.

int LinkedList :: isEmpty() {
  if(head == NULL) {
    return 1;
  }
  else { return 0; }
}

You now know a lot about handling a List, how to move through it, and how to find an element. You can create new ways to use the List.

If you’re still trying to figure out what to do with all these methods. Then here is what your primary() method will appear. Since we’ve followed OOP guidelines, we will create objects from the LinkedList class to create our List and later create objects of the Node class every time we wish to add a new Node into the List.

int main() {
  LinkedList L;
  //We will ask value from user, read the value and add the value to our Node
  int x;
  cout << "Please enter an integer value : ";
  cin >> x;
  Node *n1;
  //Creating a new node with data as x
  n1 = new Node(x);
  //Adding the node to the list
  L.addAtFront(n1);
}

Similarly you can also call any function of the LinkedList class. You can include as many Nodes as you’d like in your list.

You may also like:

• Coding Vs. Programming