Linked Lists

Linked list is a data structure to keep track of records whose size is not known in advance.
Compared to arrays, Linked list has many advantages:

• It does not need to know the size of list in advance.
• It is very useful if a record need frequent insertions/deletions.

But, for applications where we do not require to frequently update the records, i.e., records are almost constant, and we only need to access the contents of the records, then perhaps one should go for arrays.

Linked List is a collection of records. Each record may have a number of data associated with it. We represent a record as a Node of the linked list.
Each node consists of a number of data, and pointer to next record(node) in the list(collection of records).

The first Node of a Linked List is called the Head of Linked List.
For example,

head --> [4]--> [2]--> [5]--> NULL
In this linked list, the head points to Node having value 4, and last Node holds value 5.

Note: The Last Node in a Linked List points to NULL
This property is very useful, and is used to find the end of List.

struct Node
{
        int data1;
        char data2;
            ....
        double dataN;
        Node *next;

};

Now, lets look at a few important interview questions related to Linked List. The implementation given here uses C/C++, which is the most widely accepted language in almost all of the interviews.


Q1. Print the elements of a Linked List.
Solution:

// C++ code to reverse a Linked List
/* Define a structure for the Linked List node*/
struct Node
{
    int data;    // value 
    Node *next; // pointer to next node
};

/*Function to print the elements of Linked List*/
void printLL(Node *head)
{
    Node *n = head;
    while(n)
    {
        std::cout << n->data << std::endl;
        n = n->next;
    }
}

Time Complexity: O(n)
Space Complexity : O(1)

Q2. Write an iterative code to reverse the nodes of a Singly Linked List.
Solution:

// C++ code to reverse a Linked List
/* Define a structure for the Linked List node*/
struct Node
{
    int data;    // value 
    Node *next; // pointer to next node
};

/*Function to reverse the Linked List*/
void reverseLL(Node **headRef)
{
    if(*headRef == NULL)
        return;
    if(*headRef->next == NULL)
        return;
    Node *cur = *headRef;
    Node *prev = NULL:
    Node *next;
    while(cur)
    {
        next = cur->next;
        cur->next = prev;
        prev = cur;
        cur = next;
    }
    *headRef = prev;
}

Time Complexity: O(n)
Space Complexity : O(1)


Q3. Write a recursive code to reverse the nodes of a Singly Linked List.
Solution:

/* Define a structure for the Linked List node*/
struct Node
{
    int data;    // value 
    Node *next; // pointer to next node
};

/*Function to reverse the Linked List*/
void reverseLL(Node **headRef)
{
    if(*headRef == NULL)
        return;
     
    Node *first = *headRef;
    Node *rest = first->next:    
    if(rest == NULL) 
        return;
    reverseLL(&rest);
    first->next->next = first;
    first->next = NULL;
    *headRef = rest;
}

Time Complexity: O(n)
Space Complexity : O(1)

Q4. Insert a node at the tail of a Linked List.
Solution:

/* Define a structure for the Linked List node*/
struct Node
{
    int data;    // value 
    Node *next; // pointer to next node
};

/*Function to insert a node at tail of a Linked List*/
Node* insertLast(Node *head, int data)
{
    Node *n = (Node *)malloc(sizeof(Node ));
    Node *temp = head;
    n->data = data;
    n->next = NULL;
    
    if(temp == NULL)
    {
        head = n;
        return head;
    }    
    while(temp->next != NULL)    
        temp = temp->next;
    
    temp->next = n;
    return head;
}

Time Complexity: O(n)
Space Complexity : O(1)

Q5. Insert a node at the head of a Linked List.
Solution:

/* Define a structure for the Linked List node*/
struct Node
{
    int data;    // value 
    Node *next; // pointer to next node
};

/*Function to insert a node at tail of a Linked List*/
Node* insertFirst(Node *head, int data)
{
    Node *n = (Node *)malloc(sizeof(Node ));
    n->data = data;
    n->next = head;
    head = n;
    return head;
}

Time Complexity: O(1)
Space Complexity : O(1)

Q6. Insert a node at a specific position in a Linked List.

Solution:

/* Define a structure for the Linked List node*/

struct Node

{

    int data;    // value 

    Node *next; // pointer to next node

};

/*Function to insert a node in Linked List*/

Node* insertAtPos(Node *head, int data, int position)

{

    Node *n = (Node *)malloc(sizeof(Node ));

    n->data = data;

    n->next = NULL;

    if(position == 0)

    {

        n->next = head;

        head = n;

        return head;

    }    

    Node *prev = head;

    while(position > 1)

    {

        prev = prev->next;

        position--;

    }

    Node *_next = prev->next;

    prev->next = n;

    n->next = _next;

    

    return head;

}

Time Complexity: O(n)

Space Complexity : O(1)

Q7. Delete a node from a Linked List.

Solution:

/* Define a structure for the Linked List node*/

struct Node

{

    int data;    // value 

    Node *next; // pointer to next node

};

/*Function to delete a node from a Linked List*/

Node* Delete(Node *head, int position)
{
    Node *temp = head;
    Node *prev = NULL;
    if(position == 0)
    {
        head = head->next;
        return head;
    }    
    while(position > 0)
    {        
        position--;
        prev = temp;
        temp = temp->next;
    }
    prev->next = temp->next;
    return head;
}

Time Complexity: O(n)

Space Complexity : O(1)