Question

Use this implementation of Integer node,

public class IntegerNode {
public int item;
public IntegerNode next;

public IntegerNode(int newItem) {
item = newItem;
next = null;
} // end constructor

public IntegerNode(int newItem, IntegerNode nextNode) {
item = newItem;
next = nextNode;
} // end constructor
} // end class IntegerNode

You need to implement add( ), delete( ), traverse( ) methods for an ordered linked list. And after insertion and deletion, your linked list will remain ordered.

Your code should include comments and documentation.

Testing

Here is the procedure for testing, which must be documented (a Word document is preferred, as is the use of screenshots).

• Add the numbers 2, 3, and 6 to the list
• Display the list contents
• Add 5 to the list
• Display the list contents
• Delete 3 from the list
• Display the list contents
• Delete 2 from the list
• Display the list contents

Answer 1

I believe ordered linked list is sorted one.

So i will help you out with all three methods, on behalf of sorted linked list.

Lets take a look at these methods,

class IntegerNode {

        int data; // or you can use item as written in your question, its just a variable name

IntegerNode next;

IntegerNode(int d)

        {

            data = d;

            next = null;

        }

    }

    /* function to insert a

new_node in a list. */

    void sortedInsert(IntegerNode new_node)

    {

IntegerNode current;

        /* Special case for head node */

        if (head == null || head.data

>= new_node.data) {

            new_node.next = head;

            head = new_node;

        }

        else {

            /* Locate the node before point of insertion. */

            current = head;

            while (current.next != null

&& current.next.data < new_node.data)

                current = current.next;

            new_node.next = current.next;

            current.next = new_node;

        }

    }

    /*Utility functions*/

    /* Function to create a node */

IntegerNode newNode(int data)

    {

IntegerNode newNode = new Node(data);

        return newNode;

    }

Just take a look at above function, it inserts the data into a give sorted list, and after insertion order remains the same

​​​​​​DELETION FUNCTION

void deleteNode(int value)

    {

        // Store head node

IntegerNode temp = head, prev = null;

        // If head node itself holds the key to be deleted

        if (temp != null && temp.data == value)

        {

            head = temp.next; // Changed head

            return;

        }

        // Search for the key to be deleted, keep track of the

        // previous node as we need to change temp.next

        while (temp != null && temp.data != value)

        {

            prev = temp;

            temp = temp.next;

        }   

        // If key was not present in linked list

        if (temp == null) return;

        // Unlink the node from linked list

        prev.next = temp.next;

    }

NOTE : deletion function is same for all the linked list, if some node of particular value needs to be deleted.

TRAVERSING FUNCTION

public void printList()

    {

IntegerNode myHead = head;

        while (myHead != null)

        {

            System.out.print(myHead.data+" ");

MyHead = myHead.next;

        }

    }

Now, you just put all these functions, together and have fun

Also, try to name variables according to your needs, and give them meaning full names, it will help you out later.

Hope i helped you.

Happy Learning.

​​​​

​​