單向鏈表的結(jié)構(gòu)
單向鏈表.png
Node節(jié)點
static class Node<E> {
E element;
Node<E> next;
public Node(E element, Node<E> next) {
this.element = element;
this.next = next;
}
}
根據(jù)index獲取節(jié)點
private Node<E> node(int index) {
rangeCheckFor(index);
Node<E> node = first;
for (int i = 0; i < index; i++) {
node = node.next;
}
return node;
}
添加
public void add(int index, E element) {
rangeCheckForAdd(index);
if (index == 0) {
first = new Node<>(element, first);
} else {
Node<E> node = node(index - 1);
node.next = new Node<>(element, node.next);
}
size++;
}
刪除
public E remove(int index) {
rangeCheckFor(index);
Node<E> node = first;
if (index == 0) {
first = first.next;
} else {
Node<E> pre = node(index - 1);
node = pre.next;
pre.next = node.next;
}
size--;
return node.element;
}
獲取index位置的元素
public int indexOf(E element) {
Node<E> node = first;
if (element == null) {
for (int i = 0; i < size; i++) {
if (node.element == null) { return i; }
node = node.next;
}
} else {
for (int i = 0; i < size; i++) {
if (element.equals(node.element)) { return i; }
node = node.next;
}
}
return ELEMENT_NOT_FOUND;
}
清空
public void clear() {
first = null;
size = 0;
}
虛擬頭節(jié)點的單向鏈表
- 觀察代碼我們發(fā)現(xiàn)很多時候我們都需要針對頭節(jié)點做單獨處理
- 為了減少代碼的復(fù)雜度 我們可以加一個虛擬頭節(jié)點
- 添加 刪除邏輯會簡化不少
public SingleLinkedList() {
first = new Node<>(null, null);
}
