Linear Linked List


In a linear linked list we can insert element either at the beginning of the list or at the ending of the list. Consider the following code in which we have created node class:

CODE:

class Node {

  public:

  int obj;

  node * next;

  node () {

    obj = 0;

    next = NULL;

  }

  node (int a) {

    obj = a;

    next = NULL;

  }

}

Now consider the following code in which we are getting data and setting data for obj and for next pointer:

CODE:

int gettingData () {

  return obj;

}

void settingData (int d) {

  this. obj = d;

}

node* gettingNext () {

  return next;

}

void settingNext (node *p) {

  this. next = p;

}


Linked List Class:

Consider the following lines of code in which we have created a class for linked list and its methods are declared:

CODE:

class LinkedList {

  public:

  node *head;

  int InsertingAtFront (node *p);

  int isEmpty ();

  int InsertingAtEnd(node *n);

  node* searching (int d);

  node* deletingNode (int x);

  LinkedList() {

    head = NULL;

  }

}

In the above code the method int InsertingAtFront (node *p) is declared to insert the elements at front, the method int isEmpty () will be used to whether linked list is empty or not. The method int InsertingAtEnd(node *n) is declared to insert elements at the end. The method node* searching (int d) will be used to search for a value in the linked list and the method node* deletingNode (int x) will be used to delete any node from the linked list.


Insertion at the beginning:

Consider the following code to insert an element at the beginning of the linked list:

CODE:

int LinkedList :: InsertingAtFront (node *p)

{

  int x = 0;

  p -> next = head;

  head = p;

  x ++;

  return x;

}

In the above code, first the head node is created for the linked list and the linked list only has head which is null.


Inserting at the End:

Consider the following code to insert element at the end of the linked list:

CODE:

int LinkedList :: InsertingAtEnd (node *p) {

  if (head == NULL) {

    head = p;

    p -> next = NULL;

  }

  else {

    node *p2 = LastNode ();

    p2 -> next = n;

  }

}

node* LinkedList :: LastNode () {

  node* pointer = head;

  while (pointer -> next != NULL)

{

    pointer = pointer -> next;

  }

  return pointer;

}

In the above code, if the linked list is empty then we will make the new node as the head node of the linked list. And if the linked list is not empty, then the last node is found and we will make the new node to be next of last node in this way new node will be the last node.


Searching for an element in the list:

To search an element in the list, we will traverse through the list and will compare the data in the list with the element to be found. If node is found, it will be returned. If node is not found, pointer will point to the next node. Consider the following code to search for an element in the linked list:

CODE:

node* LinkedList :: searching (int a) {

  node *pointer = head;

  while (pointer != NULL && pointer -> data != a) {

    pointer = pointer -> next;

  }

  return ptr;

}


Deleting a node from list:

Consider the following code to delete the data from the linked list:

CODE:

node* LinkedList :: deletindNode (int a) {

  node *p = searching (a);

  node *pointer = head;

  if(pointer == p) {

    pointer -> next = p -> next;

    return p;

  }

  else {

    while(pointer -> next != p) {

      pointer = pointer -> next;

    }

    pointer -> next = p -> next;

    return p;

  }

}

In the above code first we searched for the node which has the same data as ‘a’. If the first node is the one to be deleted then the next node will be set as head node.


Checking whether the list is empty or not:

Consider the following code to check if the list is empty or not:

CODE:

int LinkedList :: isEmpty () {

  if (head == NULL) {

    return 1;

  }

  else

{

return 0;

}

}