patternjavaMinor
Singly linked list delete() method
Viewed 0 times
deletemethodsinglylistlinked
Problem
I would like a quick review on my method to delete a node from a singly linked list. I'm fairly certain that this is not near optimally done, and would love to get feedback.
It uses a
The element definitions and the delete function are as so:
```
import data_structures.LinkedLists.SinglyLinkedNode;
public class SinglyLinkedList{
private SinglyLinkedNode head = null;
private SinglyLinkedNode tail = null;
private int length = 0;
public SinglyLinkedList(int data){
this.head = new SinglyLinkedNode(data);
this.tail = this.head;
this.length = 1;
}
public void delete(int data){
SinglyLinkedNode n = this.head;
if (n==null){
return;
}
if (n.getData()==data){//If the head is the data we want
if (n.getNext()==null){//If it's the only node, null the head and tail
this.tail = null;
this.head = null;
this.length = 0;
}
else {//Or move the head to the next node
this.head = n.getNext();
this.length--;
}
return;
}
while (n.getNext()!=null && n.getNext().getData()!=data){//Get the data node or the last node at n.next
n=n.getNext();
}
if (n.getNext() == null){//If n is the last element in the list
if (n.getData()!=data){//If data wasn't in array then we're done
return;
}
//If we're deleting the only remaining element
if (this.length <=1)
It uses a
SinglyLinkedNode element as the node:public class SinglyLinkedNode {
private SinglyLinkedNode next = null;
int data;
public SinglyLinkedNode(int data){
this.data=data;
}
public int getData(){
return this.data;
}
public void setNext(SinglyLinkedNode next){
this.next = next;
}
public SinglyLinkedNode getNext(){
return this.next;
}
}The element definitions and the delete function are as so:
```
import data_structures.LinkedLists.SinglyLinkedNode;
public class SinglyLinkedList{
private SinglyLinkedNode head = null;
private SinglyLinkedNode tail = null;
private int length = 0;
public SinglyLinkedList(int data){
this.head = new SinglyLinkedNode(data);
this.tail = this.head;
this.length = 1;
}
public void delete(int data){
SinglyLinkedNode n = this.head;
if (n==null){
return;
}
if (n.getData()==data){//If the head is the data we want
if (n.getNext()==null){//If it's the only node, null the head and tail
this.tail = null;
this.head = null;
this.length = 0;
}
else {//Or move the head to the next node
this.head = n.getNext();
this.length--;
}
return;
}
while (n.getNext()!=null && n.getNext().getData()!=data){//Get the data node or the last node at n.next
n=n.getNext();
}
if (n.getNext() == null){//If n is the last element in the list
if (n.getData()!=data){//If data wasn't in array then we're done
return;
}
//If we're deleting the only remaining element
if (this.length <=1)
Solution
That's a very lengthly piece of code. To delete a Node, it's not about doing something confusing; it's about changing links around. Imaging this list:
In this case,
How? Well...
-
Rewrite the method so that it returns a
-
Handle special case
-
Loop until you find the data:
-
Relink the nodes:
-
End the method:
Result:
1, 2, 3, 4, 5In this case,
1 links to 2, which links to 3, and so on. So what if you want to remove 3, for example? Well, change the links so that 2 links to 4!How? Well...
-
Rewrite the method so that it returns a
boolean depending on if the delete was a success:public boolean delete(int data) {-
Handle special case
head and empty list:SinglyLinkedNode nodeBeforeDelete = this.head;
if (nodeBeforeDelete == null) { // List in empty
return false;
} else if (nodeBeforeDelete.getData() == data) {
this.head = this.head.getNext();
return true;
}-
Loop until you find the data:
while (true) {
SinglyLinkedNode next = nodeBeforeDelete.getNext()
if (next == null) { // No data found in list
return false;
} else if (next.getData() == data) {
break;
}
nodeBeforeDelete = next;
}-
Relink the nodes:
SinglyLinkedNode next = nodeBeforeDelete.getNext();
nodeBeforeDelete.setNext(next.getNext());
next.setNext(null);-
End the method:
return true;
}Result:
public boolean delete(int data) {
SinglyLinkedNode nodeBeforeDelete = this.head;
if (nodeBeforeDelete == null) { // List in empty
return false;
} else if (nodeBeforeDelete.getData() == data) {
this.head = this.head.getNext();
return true;
}
while (true) {
SinglyLinkedNode next = nodeBeforeDelete.getNext()
if (next == null) { // No data found in list
return false;
} else if (next.getData() == data) {
break;
}
nodeBeforeDelete = next;
}
SinglyLinkedNode next = nodeBeforeDelete.getNext();
nodeBeforeDelete.setNext(next.getNext());
next.setNext(null);
return true;
}Code Snippets
1, 2, 3, 4, 5public boolean delete(int data) {SinglyLinkedNode nodeBeforeDelete = this.head;
if (nodeBeforeDelete == null) { // List in empty
return false;
} else if (nodeBeforeDelete.getData() == data) {
this.head = this.head.getNext();
return true;
}while (true) {
SinglyLinkedNode next = nodeBeforeDelete.getNext()
if (next == null) { // No data found in list
return false;
} else if (next.getData() == data) {
break;
}
nodeBeforeDelete = next;
}SinglyLinkedNode next = nodeBeforeDelete.getNext();
nodeBeforeDelete.setNext(next.getNext());
next.setNext(null);Context
StackExchange Code Review Q#112396, answer score: 4
Revisions (0)
No revisions yet.