Linked List C++

Posted: March 9, 2014 in Programming
Tags: , , , , , , , , , ,

WHAT IS LINKED LIST :

Linked list is a data structure which contains a set of elements linked to its successor.

WHERE TO USE LINKED LIST :

When there is a need of lot of insertions and deletions , linked list is preferred over Array .

One simple example is this : Say we have array of 1000 numbers . 2 to 1001 . Now we need to insert 1 at the beginning of the array. Its not so simple, we need to shift all the numbers from 2 to 1001 one step right for inserting one element at the beginning.

Linked list over comes this problem. Just allocate memory and play with pointers to give connections. 1 will be inserted at the beginning.

WHERE NOT TO USE LINKED LIST :

There are certain scenarios where in we need more number of searches than insert and delete. On such occasion arrray gives us a better result.

HOW TO IMPLEMENT LINKED LIST :

In this post we will be discussing 12 basic set of items on linked list

1. Structure of Linked List

2. Creating One node Linked List

3. Creating 3 Node Linked List

4. Creating N Node linked List

5. Inserting a node at front of linked list

6. Inserting a node at end of linked list

7. Inserting a node at N point of linked list

8. Deleting first element from list

9. Deleting last element from list

10. Deleting random element from list

11. Searching linked list

12. Copying Linked list

STRUCTURE OF LINKED LIST

                       Structure Of Linked List

A linked list contains data element along with the pointer which points to the next element.

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

Creating One node Linked List:

                                         Single Node Linked List

Lets create a simple one node linked list . For creating a node , we need to follow three steps.

  1. Create a new node pointer
  2. Allocate memory and insert element
  3. Point the pointer to appropriate position
#include  // for cout
#include  // for malloc

using namespace std;

// create the struture of linked list

struct node
{
        int data;
        struct node* next;
};
void print_ll(struct node* head);

int main()
{
        // create head pointer
        struct node* head = NULL;

        // allocate memory to it
        head = (struct node*) malloc(sizeof(struct node));

        // insert the data
        head->data = 1;

        // point the next pointer
        head->next = NULL;

        // printing the list
        print_ll(head);
        return 0;
}

void print_ll(struct node* head)
{
        struct node* current = head;
        cout << "List contains" <<endl;
        while(current != NULL)
        {
                cout << current->data << endl;
                current = current->next;
        }
}

Output of single node linked list

CREATING 3 NODE LINKED LIST

                                    three_node_ll

Now, we know the size of linked list. So, lets create a function that will build 3 nodes in a linked list.

#include <iostream> // for cout
#include <stdlib.h> // for malloc

using namespace std;

// create the struture of linked list

struct node
{
        int data;
        struct node* next;
};
void print_ll(struct node* head);
struct node* three_node_ll();

int main()
{
        // call the function to create the list
        struct node* head = three_node_ll();
        // printing the list
        print_ll(head);
        return 0;
}

struct node* three_node_ll()
{
        // create 3 pointers for 3 nodes
        struct node* head = NULL;
        struct node* second = NULL;
        struct node* third = NULL;

        // allocate memory for 3 nodes
        head = (struct node*) malloc(sizeof(struct node));
        second = (struct node*) malloc(sizeof(struct node));
        third = (struct node*) malloc(sizeof(struct node));

        // insert data into 3 nodes and point the sequence in right order
        head->data = 1;
        head->next = second;

        second->data = 2;
        second->next = third;

        third->data = 3;
        third->next = NULL;

        return head;

}

void print_ll(struct node* head)
{
        struct node* current = head;
        cout << "List contains" <<endl;
        while(current != NULL)
        {
                cout << current->data << endl;
                current = current->next;
        }
}

three_node_output

CREATING N NODE LINKED LIST

In the previous case, we know the definite size of linked list . But , now we need to build a list based on the input given by the user. Hence , we need to write a generic function which will insert the numbers into list dynamically.It is easy to push elements at the front of the list . It comprises of 3 steps.

  1. Allocate memory for the new node and insert data into it.
  2. Point the next pointer to old head
  3. Change head to new node
#include <iostream> // for cout
#include <stdlib.h> // for malloc

using namespace std;

// create the struture of linked list

struct node
{
        int data;
        struct node* next;
};
void print_ll(struct node* head);
void n_node_ll(struct node*&,int);
int num_of_nodes;

int main()
{
        cout << "Enter number of nodes to be created " << endl;
        cin >> num_of_nodes;
        struct node* head = NULL;
        // call the function to create the list
        for(int i=0 ; i<num_of_nodes; i++)
        {
                n_node_ll(head,i+1);
        }
        // printing the list
        print_ll(head);
        return 0;
}

void n_node_ll(struct node*& head, int d)
{
        // allocate memory and insert data
        struct node* newNode = (struct node*) malloc(sizeof(struct node));
        newNode->data = d;
        // point next pointer to old head
        newNode->next = head;
        // point head to new node
        head = newNode;
}

void print_ll(struct node* head)
{
        struct node* current = head;
        cout << "List contains" <<endl;
        while(current != NULL)
        {
                cout << current->data << endl;
                current = current->next;
        }
}

INSERTING NODE AT FRONT OF LINKED LIST

n_node_ll

Say, we have linked list with 2 elements . 4 and 3 . Now we need to push 5 into the list at the front .

As explained in the previous code , it will be done with same 3 steps.

#include <iostream> // for cout
#include <stdlib.h> // for malloc

using namespace std;

// create the struture of linked list

struct node
{
        int data;
        struct node* next;
};
void print_ll(struct node* head);
struct node* two_node_ll();
void insert_at_front(struct node*&,int);

int main()
{
        // call the function to create the list
        struct node* head = two_node_ll();
        // inserting number 5 at the front
        insert_at_front(head,5);
        // printing the list
        print_ll(head);
        return 0;
}

void insert_at_front(struct node*& head,int d)
{
        struct node* current = head;

        // create node and allocate memory
        struct node* newNode = (struct node*)malloc(sizeof(struct node));

        //insert data into the memory
        newNode->data = d;

        // point the next pointer to old head
        newNode->next = head;

        // change head of the list to new node
        head = newNode;
}

struct node* two_node_ll()
{
        // create 3 pointers for 3 nodes
        struct node* head = NULL;
        struct node* second = NULL;

        // allocate memory for 3 nodes
        head = (struct node*) malloc(sizeof(struct node));
        second = (struct node*) malloc(sizeof(struct node));

        // insert data into 3 nodes and point the sequence in right order
        head->data = 4;
        head->next = second;

        second->data = 3;
        second->next = NULL;

        return head;

}

void print_ll(struct node* head)
{
        struct node* current = head;
        cout << "List contains" <<endl;
        while(current != NULL)
        {
                cout << current->data << endl;
                current = current->next;
        }
}

insert_at_front

INSERTING A NODE AT END OF THE LIST

insert_at_end

For adding the node at the tail end we need to follow these steps

  1. Iterate through the list and find the point the last element in the list
  2. Create new node and insert data to it
  3. Point the next pointer of new node to null since it is going to be the last element
  4. Link the old last element pointer to new node
#include <iostream> // for cout
#include <stdlib.h> // for malloc

using namespace std;

// create the struture of linked list

struct node
{
        int data;
        struct node* next;
};
void print_ll(struct node* head);
struct node* two_node_ll();
void insert_at_end(struct node*&,int);

int main()
{
        // call the function to create the list
        struct node* head = two_node_ll();

        // inserting number 3 at the end
        insert_at_end(head,3);

        // printing the list
        print_ll(head);
        return 0;
}
void insert_at_end(struct node*& head,int d)
{
        struct node* current = head;
        while(current->next != NULL)
        {
                current = current->next;
        }

        // create node and allocate memory
        struct node* newNode = (struct node*)malloc(sizeof(struct node));

        //insert data into the memory
        newNode->data = d;

        // point the next pointer to null since its the last element
        newNode->next = NULL;

        // change head of the list to new node
        current->next = newNode;
}

struct node* two_node_ll()
{
        // create 3 pointers for 3 nodes
        struct node* head = NULL;
        struct node* second = NULL;

        // allocate memory for 3 nodes
        head = (struct node*) malloc(sizeof(struct node));
        second = (struct node*) malloc(sizeof(struct node));

        // insert data into 3 nodes and point the sequence in right order
        head->data = 5;
        head->next = second;

        second->data = 4;
        second->next = NULL;

        return head;

}

void print_ll(struct node* head)
{
        struct node* current = head;
        cout << "List contains" <<endl;
        while(current != NULL)
        {
                cout << current->data << endl;
                current = current->next;
        }
}

output_insert_at_end

 

 

 

 

Advertisements

Comments are closed.