[TOC]
# 代码
~~~
public class LinkedList<E> {
//不需要知道node是怎么实现
private class Node {
//元素
public E e;
//下一个元素的位置
public Node next;
public Node(E e, Node next) {
this.e = e;
this.next = next;
}
public Node(E e) {
this(e, null);
}
public Node() {
this(null, null);
}
@Override
public String toString() {
return e.toString();
}
}
//虚拟头节点
private Node dummyHead;
//大小不允许外部修改
private int size;
public LinkedList() {
//初始是什么都没有
dummyHead = new Node(null, null);
size = 0;
}
//返回链表是否为空
public boolean isEmpty() {
return size == 0;
}
//在链表的index(0-based)位置添加新的元素e
//在链表中不是一个常用的操作
public void add(int index, E e) {
//index是要插入的位置
if (index < 0 || index > size) {
//这个位置不能是负的,或者比链表的最大值要大
throw new IllegalArgumentException("Add failed.Illegal index.");
}
//先把前面一个元素的位置置为虚拟头元素
Node prev = dummyHead;
//前面一个元素就是index,因为是从dummyHead遍历的
for (int i = 0; i < index; i++) {
//找到了就赋值给前面一个元素
prev = prev.next;
}
//创建节点
Node node = new Node(e);
//把原来这位置的指向下一个元素拿来给自己
node.next = prev.next;
//前面一个元素的指向下一个就是自己了
prev.next = node;
//可以简化这一步
// prev.next = new Node(e, prev.next);
//维护下链表大小
size++;
}
//在链表头添加新的元素e
public void addFirst(E e) {
add(0, e);
}
//在链表末尾添加新的元素e
public void addLast(E e) {
add(size, e);
}
// 获取链表中的元素个数
public int getSize(){
return size;
}
//获取第index个位置的索引
public E get(int index) {
if (index < 0 || index > size) {
//这个位置不能是负的,或者比链表的最大值要大
throw new IllegalArgumentException("Get failed.Illegal index.");
}
Node cur = dummyHead.next;
for (int i = 0; i < index; i++) {
cur = cur.next;
}
return cur.e;
}
//获得链表第一个元素
public E getFirst() {
return get(0);
}
//获得链表的最后一个元素
public E getLast() {
return get(size - 1);
}
//修改链表中的第index个位置的元素为e
public void set(int index, E e) {
if (index < 0 || index > size) {
//这个位置不能是负的,或者比链表的最大值要大
throw new IllegalArgumentException("Update failed.Illegal index.");
}
Node cur = dummyHead.next;
for (int i = 0; i < index; i++) {
cur = cur.next;
}
cur.e = e;
}
//查找链表中是否有元素e
public boolean contains(E e) {
Node cur = dummyHead.next;
while (cur != null) {
if (cur.e.equals(e)) {
return true;
}
cur = cur.next;
}
return false;
}
//删除元素
public E remove(int index) {
if (index < 0 || index > size) {
//这个位置不能是负的,或者比链表的最大值要大
throw new IllegalArgumentException("Remove failed.Illegal index.");
}
Node prev = this.dummyHead;
for (int i = 0; i < index; i++) {
prev = prev.next;
}
//要删除的元素
Node retNode = prev.next;
//把要删除的下一个节点拼接到上一个节点的后面
prev.next = retNode.next;
//要删除的元素,被gc
retNode.next = null;
//维护长度
size--;
return retNode.e;
}
//删除第一个元素,返回删除的元素
public E removeFirst() {
return remove(0);
}
//从链表中删除最后一个元素,返回删除的元素
public E removeLast() {
return remove(size - 1);
}
@Override
public String toString() {
StringBuilder res = new StringBuilder();
Node cur = dummyHead.next;
while (cur != null) {
res.append(cur + "->");
cur = cur.next;
}
res.append("NULL");
return res.toString();
}
}
~~~
# 测试
~~~
public static void main(String[] args) {
LinkedList<Integer> linkedList = new LinkedList<Integer>();
for (int i = 0; i < 5; i++) {
linkedList.addFirst(i);
System.out.println(linkedList);
}
linkedList.add(2, 666);
System.out.println(linkedList);
linkedList.remove(2);
System.out.println(linkedList);
}
~~~
# 时间复杂度分析
添加操作
~~~
addLast(e) O(n)
addFirst(e) O(1)
add(index,e) O(n/2) = O(n)
~~~
删除操作
~~~
removeLast(e) O(n)
removeFirst(e) O(1)
remove(index,e) O(n/2)=O(n)
~~~
修改操作
~~~
set(index,e) O(n)
~~~
查找操作
~~~
get(index) O(n)
contains(e) O(n)
~~~
链表不适合做修改
