单链表结构如下图:
单链表.jpg
单增.png
首先定义节点的数据格式：
一个节点包含存储的元素，指向上个节点的对象，指向下个节点的对象
class Node {
public Node pre;
public Node next;
public T item;
public Node(Node pre, Node next, T item) {
super();
this.pre = pre;
this.next = next;
this.item = item;
}
}
链表数据结构只需要明确知道第一个节点，即可获取整个链表中的节点，并做对应的数据处理，所以在类中定义第一个节点与最后一个节点(方便添加元素)，size 用于存储节点总数
private Node first;
private Node last;
private int size = 0;
重点在于添加方法：
public void add(int index, T obj) {
if (index >= size || index < 0) {
throw new ArrayIndexOutOfBoundsException();
}
if (index == 0) {
addFirst(obj);
} else if (index == size) {
addLast(obj);
} else {
// 需要后移的节点
Node needPostNode = searchNode(index);
// 需被插入的节点
Node node = new Node(needPostNode.pre, needPostNode, obj);
// 前一节点的next指向需被插入的节点
needPostNode.pre.next = node;
// 需要后移的节点的pre指向被插入的节点
needPostNode.pre = node;
size++;
}
}
searchNode方法使用一个循环获取需要后移的节点
private Node searchNode(int index) {
if (index >= size || index < 0) {
throw new ArrayIndexOutOfBoundsException();
}
int i = 0;
Node popNode = first;
while (i < index) {
popNode = popNode.next;
i++;
}
return popNode;
}
完整代码如下:
public class MyLinkedList<T> {
private Node first;
private Node last;
private int size = 0;
public int size() {
return size;
}
public T get(int index) {
if (index >= size || index < 0) {
throw new ArrayIndexOutOfBoundsException();
}
return searchNode(index).item;
}
public void remove(T obj) {
if (size == 0) {
return;
}
int index = 0;
Node popNode = first;
while (index < size) {
if (popNode.item.equals(obj)) {
remove(index);
break;
}
popNode = popNode.next;
index++;
}
}
public void remove(int index) {
if (index >= size || index < 0) {
throw new ArrayIndexOutOfBoundsException();
}
if (index == 0) {
removeFirst();
} else if (index == size - 1) {
removeLast();
} else {
// 需要删除的节点
Node needPopNode = searchNode(index);
// 上一个节点的next指向需要删除的节点的下一个节点
needPopNode.pre.next = needPopNode.next;
// help gc
needPopNode = null;
size--;
}
}
public void removeFirst() {
if (size == 0) {
throw new RuntimeException("the list have not element");
}
if (size == 1) {
first = null;
last = null;
} else {
// 第二个节点的pre指向null
first.next.pre = null;
// 第一个节点指向第二个节点
first = first.next;
}
size--;
}
public void removeLast() {
if (size == 0) {
throw new RuntimeException("the list have not element");
}
if (size == 1) {
first = null;
last = null;
} else {
// 最后第二个节点的next指向null
last.pre.next = null;
// 最后第一个节点指向最后第二个节点
last = last.pre;
}
size--;
}
public void add(T obj) {
addLast(obj);
}
public void add(int index, T obj) {
if (index >= size || index < 0) {
throw new ArrayIndexOutOfBoundsException();
}
if (index == 0) {
addFirst(obj);
} else if (index == size) {
addLast(obj);
} else {
// 需要后移的节点
Node needPostNode = searchNode(index);
// 需被插入的节点
Node node = new Node(needPostNode.pre, needPostNode, obj);
// 前一节点的next指向需被插入的节点
needPostNode.pre.next = node;
// 需要后移的节点的pre指向被插入的节点
needPostNode.pre = node;
size++;
}
}
private Node searchNode(int index) {
if (index >= size || index < 0) {
throw new ArrayIndexOutOfBoundsException();
}
int i = 0;
Node popNode = first;
while (i < index) {
popNode = popNode.next;
i++;
}
return popNode;
}
/**
* 在头部添加
*
* @param obj
*/
public void addFirst(T obj) {
if (last == null) {
Node node = new Node(null, null, obj);
first = node;
last = node;
} else {
// 需被插入的节点
Node node = new Node(null, first, obj);
// 当前第一个节点的pre指向需被插入的节点
first.pre = node;
// 当前第一个节点指向被插入的节点
first = node;
}
size++;
}
/**
* 在尾部添加
*
* @param obj
*/
public void addLast(T obj) {
if (last == null) {
Node node = new Node(null, null, obj);
first = node;
last = node;
} else {
// 需被插入的节点
Node node = new Node(last, null, obj);
// 当前最后节点的next指向需被插入的节点
last.next = node;
// 当前最后节点指向被插入的节点
last = node;
}
size++;
}
/**
* 链表节点
*
* @author aruba
*
*/
class Node {
public Node pre;
public Node next;
public T item;
public Node(Node pre, Node next, T item) {
super();
this.pre = pre;
this.next = next;
this.item = item;
}
}
}
总结
链表在做元素的增加删除工作时效率非常高，只需要改变节点的指向，而在取数据是，每次都要进行一个循环来找到对应的元素。
