Following code snippet contains various remove() methods, taken from one of my LinkedList implementation, written in Java.
Code
LinkedList.java (partly)
private int size; // node count,
private LinkedListNode<T> head; // first node,
private LinkedListNode<T> end; // last node,
/**
* Remove by index.
*
* @param k index, start from 0,
* @return value of removed node, or null if not removed,
*/
@Override
public T remove(int k) {
checkElementIndex(k);
// find target node, and remember previous node,
LinkedListNode<T> preNode = null;
LinkedListNode<T> node = head;
while (k-- > 0) {
preNode = node;
node = node.next;
}
T result = (T) node.value; // keep return value,
removeNode(node, preNode); // remove
return result;
}
/**
* Remove by value, only remove the first occurrence, if any.
*
* @param v
* @return whether removed,
*/
@Override
public boolean removeValue(T v) {
// find target node, and remember previous node,
LinkedListNode<T> preNode = null;
LinkedListNode<T> node = head;
while (true) {
if (node == null) return false;// not found,
if (node.getValue().compareTo(v) == 0) break; // value found,
preNode = node;
node = node.next;
}
removeNode(node, preNode); // remove
return true;
}
/**
* Remove by value, remove all occurrences.
*
* @param v
* @return count of nodes removed,
*/
@Override
public int removeAllValue(T v) {
int rc = 0;
// find target node, and remember previous node,
LinkedListNode<T> preNode = null;
LinkedListNode<T> node = head;
while (true) {
if (node == null) return rc; // reach end,
if (node.getValue().compareTo(v) == 0) { // value found,
rc++;
if (removeNode(node, preNode)) break; // remove, break if it's end,
continue; // recheck this node, since it become the next node,
}
preNode = node;
node = node.next;
}
return rc;
}
/**
* Remove given node, which guarantee to exists. Also reduce the size by 1.
*
* @param node node to delete,
* @param preNode previous node, could be null,
* @return indicate whether removed node is end,
*/
protected boolean removeNode(LinkedListNode node, LinkedListNode preNode) {
LinkedListNode nextNode = node.next; // next node,
boolean isEnd = (nextNode == null);
if (isEnd) { // target is end,
if (preNode == null) { // target is also head,
head = null;
} else { // target is not head, thus preNode is not null,
preNode.next = null;
}
end = preNode;
} else { // target is not end,
// replace target with next node,
node.next = nextNode.next;
node.value = nextNode.value;
}
size--; // reduce size by 1,
return isEnd;
}
/**
* Remove head node,
*
* @return
*/
@Override
public T removeHead() {
return remove(0);
}
/**
* Remove end node,
*
* @return
*/
@Override
public T removeEnd() {
return remove(size - 1);
}
LinkedListTest.java (partly)
(unit test, via TestNG)
import org.testng.Assert;
import org.testng.annotations.BeforeMethod;
import org.testng.annotations.Test;
/**
* LinkedList test.
*
* @author eric
* @date 1/28/19 6:03 PM
*/
public class LinkedListTest {
private int n = 10;
private LinkedList<Integer> llist; // linked list,
private LinkedList<Integer> dupEvenLlist; // linked list, with duplicated even values,
@BeforeMethod
public void init() {
// init llist,
llist = new LinkedList(); // create linked list,
Assert.assertTrue(llist.isEmpty());
LinkedList.appendRangeNum(llist, 0, n); // append range,
// init dupEvenLlist,
dupEvenLlist = new LinkedList(); // create linked list,
LinkedList.appendRangeNum(dupEvenLlist, 0, n); // append range,
LinkedList.appendRangeNum(dupEvenLlist, 0, n, 2); // append range, again, with step as 2 (only even numbers),
Assert.assertEquals(dupEvenLlist.size(), n + n / 2);
}
// non-remove related test cases ... are deleted,
// remove(k) - remove by index,
@Test
public void testRemoveByIndex() {
for (int i = 0; i < n; i++) {
Assert.assertEquals(llist.removeEnd().intValue(), n - 1 - i); // remove by end, in turn it remove by index,
Assert.assertEquals(llist.size(), n - 1 - i);
}
Assert.assertTrue(llist.isEmpty());
}
// remove(v) - remove by value,
@Test
public void testRemoveByValue() {
Assert.assertFalse(llist.removeValue(n)); // not exists,
for (int i = n - 1; i >= 0; i--) {
Assert.assertTrue(llist.removeValue(i)); // remove by value,
Assert.assertEquals(llist.size(), i);
}
Assert.assertTrue(llist.isEmpty());
Assert.assertFalse(llist.removeValue(0)); // empty,
// remove from list with duplicated value,
for (int i = 0; i < n; i++) {
Assert.assertTrue(dupEvenLlist.removeValue(i));
}
Assert.assertFalse(dupEvenLlist.isEmpty());
Assert.assertEquals(dupEvenLlist.size(), n / 2);
}
// removeAll(v) - remove all occurrences by value,
@Test
public void testRemoveAllByValue() {
Assert.assertEquals(dupEvenLlist.removeAllValue(n), 0); // not exists,
int remainSize = dupEvenLlist.size();
for (int i = 0; i < n; i++) {
int rc = dupEvenLlist.removeAllValue(i); // remove all by value,
Assert.assertEquals(rc, i % 2 == 0 ? 2 : 1);
remainSize -= rc;
Assert.assertEquals(dupEvenLlist.size(), remainSize);
}
Assert.assertTrue(dupEvenLlist.isEmpty());
Assert.assertEquals(dupEvenLlist.removeAllValue(0), 0); // empty,
}
}
All test cases would pass.
Explanation
Methods:
T remove(int k), remove by index.
Steps:
* loop to target node,
* for each step,
record:
* previous node,
* this node,
* get next node, of target node,
* get value of target node,
as return value later,
* if target is end,
* if also head,
head = null;
* if not head,
preNode.next = null;
* end = preNode;
* if targe is not end,
replace it with its next node,
logic:
* node.value = nextNode.value;
* node.next = nextNode.next;
* return previously tracked value of target node,
boolean removeValue(T v), remove by value, only remove first occurrence, if any.
The logic is similar as remove by index.
The differences are:
- At initial search, compare element instead of loop to index, to find target.
- Return boolean that indicate whether removed, instead of removed value,
int removeAllValue(T v), remove all by value, remove all occurrences.
This is similar as remove by value.
Differences:
- [inside while()]
- It will search all occurrence till end.
- After removing an occurrence, it "continue" to recheck the current node.
Because the current node has actual replaced by it's next.
- If removed node is end, then return.
This relay on the return value of removeNode().
- It record count of removed occurrence.
- [return value]
- It return count of removed occurrence, instead of boolean.
boolean removeNode(LinkedListNode node, LinkedListNode preNode), remove by node, with preNode given.
Remove given node, which is guaranteed to exists, with previous node given, which might be null.
Return value indicate whether removed node is end, it's mainly used to support removeAllValue().
T removeHead(), T removeEnd(), remove head / end.
Simply calls remove by index, with corresponding index 0 and size - 1 passed.
Tips:
LinkedList represent linkedlist, with fields size, head, end, and generic type T (for value type in node), it's not thread-safe.checkElementIndex() method, check given index, and throw exception if out of range.LinkedListNode, represent the node in linked list. with fields value, next.
Complexity
- Remove single:
O(k)
- Remove all by value:
O(n)
Where:
k, is the index of target.n, is size of linkedlist.
