China Cat my RAM

Singly Linked List – remove element

Problem:
Given a singly linked list, write a function void DeleteBefore(node **head, data). For example, if the list has values 1->3->6->7->8->9->13, if data is 7, then element with data = 6 will be removed.

As I've said before, Java's LinkedList, which is an implementation of a doubly linked list, would make solving this problem trivial, so that is exactly why I must use a singly linked list.

First, I'll create a Java object that represents an element in a singly linked list.

public class SinglyLinkedListElement {
	private int data;
	private SinglyLinkedListElement next;

	public SinglyLinkedListElement(int data) {
		this.data = data;
		next = null;
	}
	public int getValue() {
		return this.data;
	}
	public SinglyLinkedListElement getNext() {
		return this.next;
	}
	public void setNext(SinglyLinkedListElement next) {
		this.next = next;
	}
}

Next I'll (1) instantiate a SinglyLinkedListElement for each test integer creating a singly linked list and (2) remove the element before the element x (in this case, x is hard-coded to be 9).

public static void removePreviousElementSinglyLinkedList() {

    int[] testData = new int[]{1, 3, 6, 7, 8, 9, 13};
    int x = 9;

    SinglyLinkedListElement head = null;
    SinglyLinkedListElement prevElem = null;
    for (int i = 0; i < testData.length; i++) {
    	SinglyLinkedListElement newElem = new SinglyLinkedListElement(testData[i]);
    	if (head == null) {
    	    head = newElem;
    	}
    	else {
    	    prevElem.setNext(newElem);
    	}
    	prevElem = newElem;
    }

    SinglyLinkedListElement curr = head;
    SinglyLinkedListElement prevElem = null;
    SinglyLinkedListElement prevPrevElem = null;
    while (curr != null) {
    	if (curr.getValue() == x) {
    		if (prevElem == null) {
    			System.out.println("No previous element to delete");
    		}
    		else {
    			if (prevPrevElem == null) {
    				//deleting head elem, so make the curr elem the new head
    				prevElem.setNext(null);
    				head = curr;
    			}
    			else {
    				prevPrevElem.setNext(curr);
    			}
    		}
    		break;
    	}
    	else {
    		if (prevElem != null) {
    			prevPrevElem = prevElem;
    		}
    		prevElem = curr;
    	}
    	curr = curr.getNext();
    }
}