Question

Data Structures on Java

Basic Linked List exercises

a. Suppose x is a linked-list node and not the last node on the list.

What is the effect of the following code fragment?

x.next = x.next.next

b. Singly Linked List has two private instance variables first and last as that point to the first and the last nodes in the list, respectively. Write a fragment of code that removes the last node in a linked list whose first node is first. Is there any advantage of keeping the last pointer in a linked list implementation? Explain.

Answer 1

Here are solutions to (a) and (b).

Along with the solutions, sample codes are added to demonstrate working of code fragments. Also, sample output is added at the end of each program.

(a):

Given that x is a linked-list node and not the last node on the list.

Given code fragment is:

x.next = x.next.next

After the above code fragment is executed, the 'next' field of x stores the address present in the 'next' field of the node that follows 'x'.

In other words,the node 'x' no longer points to the node that was previously present after 'x'. Instead , it points to the node that follows it.

For example, let us consider three nodes x,y and z in a linked list.

Before execution of the given statement:

x -> y -> z

After execution of the given statement:

x -> z

Hence, we can say that the given code fragment removes the node that follows 'x' from the linked list. (In case of above example, the node 'y' is removed from the linked list.)

Here is a sample program to demonstrate this.

Sample program:

import java.util.LinkedList;
import java.util.List;

public class SampleList {

    public static class Node{

        String data;
        Node next;

        Node(){

        }
        Node(String data){
            this.data=data;
            this.next=null;
        }
    }

    public static class LinkedListImp{

        Node head,tail;

        LinkedListImp(){
            head=null;
            tail=null;
        }

        void insert(String data){
            Node newNode=new Node(data);
            if(head==null){
                head=newNode;
                tail=newNode;
            }
            else{
                tail.next=newNode;
                tail=newNode;
            }
        }

        void display(){

            Node temp=head;
            while(temp!=null){
                System.out.print(temp.data+"  ");
                temp=temp.next;
            }
        }

        Node getHead(){
            return head;
        }
    }

    public static void main(String[] args){

        LinkedListImp linkedList=new LinkedListImp();



        linkedList.insert("X");
        linkedList.insert("Y");
        linkedList.insert("Z");

        Node x=linkedList.getHead();

        System.out.println("The elements in linked list before execution of code fragment are:");

        linkedList.display();

        x.next=x.next.next;

        System.out.println("\nThe elements in linked list before execution of code fragment are:");

        linkedList.display();
    }
}

Output:

(b):

Here is fragment of code that removes the last node of the linked list:

Code fragment:

        if(first==null){    /*checks if the linked list is empty*/
            System.out.println("Linked list is empty");
        }
        else if(first==last){     /*checks if there is only one node in the list*/
            first=null;
            last=null;
        }
        else{
            Node temp = first;   /*creates a temp node that points to first*/
            while(temp.next!=last){     /*this loop makes temp traverse the list until temp.next=last*/
                temp=temp.next;
            }
            temp.next=null;    /*makes temp.next point to null*/
            last=temp;      /*makes last point to temp*/
        }

Advantage of keeping last pointer in a linked list implementation:

last pointer of a linked list implementation makes the insertion of new node into linked list easier.This is because if we want to add new node into the linked list, we just have to make the last node's 'next' point to new node.

If there is no last pointer, everytime a new node needs to be inserted into the list, the list should be traversed from 'first' pointer until we reach the last node of the list and then make that node point to new node.

This is time consuming, especially when the list is long.

Hence, keeping a 'last' pointer is beneficial.

Here is the code to demonstrate removal of last node from linked list:

import java.util.LinkedList;
import java.util.List;

public class SampleList {

    public static class Node{

        String data;
        Node next;

        Node(){

        }
        Node(String data){
            this.data=data;
            this.next=null;
        }
    }

    public static class LinkedListImp{

        private Node first,last;

        LinkedListImp(){
            first=null;
            last=null;
        }

        void insert(String data){
            Node newNode=new Node(data);
            if(first==null){
                first=newNode;
                last=newNode;
            }
            else{
                last.next=newNode;
                last=newNode;
            }
        }

        void display(){

            Node temp=first;
            while(temp!=null){
                System.out.print(temp.data+"  ");
                temp=temp.next;
            }
        }

        Node getFirst(){
            return first;
        }

        Node getLast(){
            return last;
        }
    }

    public static void main(String[] args){

        LinkedListImp linkedList=new LinkedListImp();



        linkedList.insert("X");
        linkedList.insert("Y");
        linkedList.insert("Z");

        System.out.println("The elements in linked list before execution of code fragment are:");

        linkedList.display();


        Node first=linkedList.getFirst();
        Node last=linkedList.getLast();

        if(first==null){    /*checks if the linked list is empty*/
            System.out.println("Linked list is empty");
        }
        else if(first==last){     /*checks if there is only one node in the list*/
            first=null;
            last=null;
        }
        else{
            Node temp = first;   /*creates a temp node that points to first*/
            while(temp.next!=last){     /*this loop makes temp traverse the list until temp.next=last*/
                temp=temp.next;
            }
            temp.next=null;    /*makes temp.next point to null*/
            last=temp;      /*makes last point to temp*/
        }

        System.out.println("\nThe elements in linked list before execution of code fragment are:");

        linkedList.display();
    }
}

Output: