Следующий фрагмент кода содержит различные remove() методы, взятые из одной из моих LinkedList реализаций, написанные в Java.
Code
LinkedList.java (частично)
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 (частично)
(модульный тест,через 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,
}
}
Все тесты пройдут.
Объяснение
Методы:
T remove(int k), удалить по индексу.
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), удалить по значению, удалить только первое вхождение, если оно есть.
Логика аналогична удалению по индексу.
Различия:
- При начальном поиске сравнивайте элемент вместо цикла с индексом, чтобы найти цель.
- Возвращает логическое значениекоторые указывают, было ли удалено вместо удаленного значения
int removeAllValue(T v), удалить все по значению, удалить все вхождения.
Это похоже на удаление по значению.
Различия:
- [ внутри while () ]
- Он будет искать все вхождения до конца.
- Послеудаляя вхождение, оно «продолжает» перепроверять текущий узел.Поскольку текущий узел фактически заменен следующим:
- Если удаленный узел является концом, верните.
Это реле с возвращаемым значением removeNode(). - Это количество записейудаленное вхождение.
- [ возвращаемое значение ]
- Возвращает счетчик удаленных вхождений вместо логического значения.
boolean removeNode(LinkedListNode node, LinkedListNode preNode), удалить по узлу, с заданным preNode.
Удалить данный узел, который гарантированно существует, с указанным предыдущим узлом, который может быть нулевым.
Возвращаемое значение указывает, является ли удаленный узел конечным, это главным образомиспользуется для поддержки removeAllValue().
T removeHead(), T removeEnd(), удаление заголовка / конца.
Просто вызывает удаление по индексу с соответствующим индексом 0 и size - 1 прошло.
Советы:
LinkedList представляют связанный список с полями size, head, end иуниверсальный тип T (для типа значения в узле), он не является потокобезопасным. checkElementIndex() метод, проверьте заданный индекс и выведите исключение, если выходит за пределы диапазона. LinkedListNode, представляет узел в связанном списке.с полями value, next.
Сложность
- Удалить один:
O(k) - Удалить все по значению:
O(n)
Где:
k, это индекс цели. n, это размер связанного списка.