Badar Shahzad Khan Badar Shahzad Khan - 29 days ago 14
Java Question

Unable to delete first item in linked list

I saw some solutions, but I am still unable to resolve the error in my code. My

deleteFromStart
method is not removing any elements from the list. Both invocations of
ob.display()
produce the same output. Can you tell me what I am missing, or where the error is?

LikedList:

package lab5;

public class LinkedList {

public static void main(String argsp[]){

List ob = new List();

ob.addAtStart("y", 6);
ob.addAtStart("w", 4);
ob.addAtStart("z", 3);

ob.addAtEnd("a",3);
ob.addAtEnd("b",4);
ob.addAtEnd("c",5);

ob.display();

ob.deleteFromStart();

System.out.println("\n");
ob.display();
}
}


List:

package lab5;

public class List {

Node head;

public List(){
head=null;
}

public List(Node e){
head=e;
}

Node oldfirst=null;
Node lasthead=null;

public void addAtStart(String name, int age){
Node newObject= new Node(name,age);
newObject.next=head;

if (oldfirst==null) {
oldfirst = newObject;
}
head = newObject;
lasthead = head;
}

public void display() {
Node store = head;
while (store != null) {
store.display();
store=store.next;
System.out.println();
}
}

public void addAtEnd(String name, int age){
Node atEndValue = new Node(name, age);
oldfirst.next = atEndValue;
oldfirst = atEndValue;
}

public void deleteFromStart() {
while (lasthead != null) {
lasthead = lasthead.next;
}
}

public boolean isEmpty() {
return head == null;
}


Node:

package lab5;

public class Node {

String name;
int age;
Node next;

public Node(){
name="Abc";
age=10;
next=null;
}

public Node(String name, int age ){
this.name=name;
this.age=age;
next = null;
}

public void display(){
System.out.println("Name: " + name + " Age: " + age);
}
}

Answer

tl;dr To remove the first element in a linked-list:

head = head.next

When you're implementing a singly-linked list, you really only need to keep a single pointer: head (i.e. a reference to the first node in the list. In practice, it's also useful to keep track of the last element in the list (commonly referred to as tail). This allows constant-time operations at the end of the list, which are useful if you're frequently adding/removing elements at the end. So, with this basic implementation, you end up with something like this:

class LinkedList {
    private Node head = null;
    private Node tail = null;

    public LinkedList() {}

    public LinkedList(Node e) {
        head = e;
        tail = e;
    }
}

class Node {
    Node next = null;
    // other data
}

Adding and removing elements in a linked list boils to down to updating what the head and tail variables are referring to. Consider a singly-linked list with three elements, [A, B, C]. The values head and tail values align like this:

 A -> B -> C -> null
 ^         ^
 |         |
head      tail

If you want to insert a new element, X, there are two steps:

1) Tell X.next to refer to A:

X -> A -> B -> C -> null
     ^         ^
     |         |
    head      tail

2) Update head to refer to X:

 X -> A -> B -> C -> null
 ^              ^
 |              |
head           tail

You move head and tail around in similar fashion, depending on whether you're adding or removing, and whether or not the operation is at the beginning or end of the list.

Removing an element from the start (assuming that the list is not empty) is as simple as updating head to refer to the next element. In our example above, this would mean moving head to refer to X.next, which is A:

X -> A -> B -> C -> null
     ^         ^
     |         |
    head      tail

Now remember, the linked list is only directly aware of head and tail, so once you update head to refer to A there is nothing referencing X anywhere in your application, and it has effectively been deleted (in Java this will cause it to be garbage-collected).

Effectively what we did above was simply head = head.next. Again, you'll have to ensure the list isn't empty first, since head.next will cause a null pointer exception if the list is empty.

I'd also suggest removing oldfirst and lasthead, and updating your add* methods based on the theory above.

Comments