Home > Blockchain >  How can I delete a value from a Linked List?
How can I delete a value from a Linked List?

Time:10-18

I am working on a project for my Data Structures class that asks me to write a class to implement a linked list of ints.

  • Use an inner class for the Node.
  • Include the methods below.
  • Write a tester to enable you to test all of the methods with whatever data you want in any order.

I have to create a method called "public boolean delete(int item)". This method is meant to "Delete an item from the list and return a Boolean indicating whether or not the item was deleted" I have my code for this method down below. However, when I try to delete an item from my list nothing changes. The item that I tried to delete is still there but it returns true that an item was deleted. Does someone know what I did wrong in my code and how to fix it?

import java.util.Random;
import java.util.Scanner;

public class LinkedListOfInts {
    Node head;
    Node tail;

    private class Node {
        int value;
        Node nextNode;

        public Node(int value, Node nextNode) {
            this.value = value;
            this.nextNode = nextNode;
        }

    }

    public LinkedListOfInts(LinkedListOfInts other) {
        Node tail = null;
        for (Node n = other.head; n != null; n = n.nextNode) {
            if (tail == null)
                this.head = tail = new Node(n.value, null);
            else {
                tail.nextNode = new Node(n.value, null);
                tail = tail.nextNode;
            }
        }
    }

    public LinkedListOfInts(int[] other) {
        Node[] nodes = new Node[other.length];
        for (int index = 0; index < other.length; index  ) {
            nodes[index] = new Node(other[index], null);
            if (index > 0) {
                nodes[index - 1].nextNode = nodes[index];
            }
        }

        head = nodes[0];
    }

    public LinkedListOfInts(int N, int low, int high) {
        Random random = new Random();
        for (int i = 0; i < N; i  )
            this.addToFront(random.nextInt(high - low)   low);
    }

    public void addToFront(int x) {
        head = new Node(x, head);
    }

    public int deleteFromFront() {
        int headValue = -1;
        if (head == null)
            return headValue;
        else {
            if (head == tail) {
                head = null;
                tail = null;
            } else {
                headValue = head.value;
                head = head.nextNode;
            }
        }
        return headValue;
    }

    public boolean delete(int item) {
        Node previous = null;
        for (Node ptr = head; ptr != null; ptr = ptr.nextNode) {
            if (ptr.value == item) {
                if (previous != null) {
                    previous = ptr;
                } else
                    deleteFromFront();
                return true;
            }
            previous = ptr;
        }
        return false;
    }

    public String toString() {
        String result = " ";
        for (Node ptr = head; ptr != null; ptr = ptr.nextNode)
            result  = ptr.value   " ";
        return result;
    }

    public static void main(String[] args) {
        Scanner input = new Scanner(System.in);
        LinkedListOfInts list = new LinkedListOfInts(10, 1, 20);
        LinkedListOfInts copy = new LinkedListOfInts(list);
        boolean done = false;
        while (!done) {
            System.out.println("1. Delete an Item in the Array");
            System.out.println("2. toString");
            switch (input.nextInt()) {
            case 11:
                System.out.println("Delete an Item in the Array");
                System.out.println(list.delete(input.nextInt()));
                break;
            case 12:
                System.out.println("toString");
                System.out.println(list.toString());
                break;
            }
        }
    }
}

CodePudding user response:

Because local variable is local. Let's go through your delete method:

Node previous = null;

This declares a new local variable named previous, which currently points at nothing. Like all local variables, and like all non-primitive variables, [A] this thing will poof out of existence once the method terminates, and [B] it's a pointer. (in java parlance, a reference). It's like an address on a slate, it's not a house. It's the address to a house.

previous = ptr;

This erases what is on your slate and copies over the house address. It doesn't copy the house, nor does it have any effect on the house whose address was on your slate before wiping out that address and copying the address of whatever the 'ptr' slate's got on it.

... method ends

... and there previous goes. In the trashcan.

a.b is java-ese for: Drive over to the address on slate 'a', and ask the house to 'b' (or change something about the house, if you're messing with fields instead of calling methods).

So, pointer = foo accomplishes nothing. head.something = foo, that does something, now you're driving. You have to drive somewhere, or change one of your fields, for this code to do anything.

previous.nextNode = ptr.nextNode; is more what you're looking for. previous is a copy of the address of the node you visited before. Changing the address on your little note isn't going to accomplish anything, you want to drive over there. previous.nextNode is: Find the scribbled address on the piece of paper named 'previous' and drive over there. Go in the house and find the box labelled 'nextNode'. Open the box, you'll find a note with an address in it. Take that address, scratch it out, and write a new address on it.

Now if somebody else, with a different piece of paper with the same address on it, drives on over and pulls that box out, they'll see what you changed.

In java, just about everthing is an address scribbled on a note and not the object itself. (the only exceptions are primitives: int, long, double, float, boolean, char, short, byte).

  • Related