一、什么是单向链表
单向链表也叫单链表，是链表中最简单的一种形式，它的每个节点包含两个域，一个信息域（元素域）和一个链接域。这个链接指向链表中的下一个节点，而最后一个节点的链接域则指向一个空值。
a、 表元素域elem用来存放具体的数据。
b、链接域next用来存放下一个节点的位置。
c、变量p指向链表的头节点（首节点）的位置，从p出发能找到表中的任意节点。
二、链表基本操作的实现原理；
（1）、添加元素；
直接添加即在链表的末尾添加，又因底层是用LinkedList实现的，所以添加的方法为List的添加方法
@Override
public void add(E element) {
add(size, element);
}（2）对应的角标处添加元素；
a、首先进行范围的判断处理如果添加的位置不在链表的范围内，则抛出异常；
b、先声明一个节点用来存储插入的元素。
c、判断插入位置，实现插入点前后的链接。
@Override
public void add(int index, E element) {
if (index < 0 || index > size) {
throw new IllegalArgumentException("add index out of range");
}
Node n = new Node(element);
if (size == 0) {
head = n;
tail = n;
} else if (index == 0) {
n.next = head;
head = n;
} else if (index == size) {
tail.next = n;
tail = n;
} else {
Node p = head;
for (int i = 0; i < index - 1; i++) {
p = p.next;
}
n.next = p.next;
p.next = n;
}
size++;
}（3）删除元素
首先判断链表中是否有该元素，获取该元素的角标。移除对应角标处的元素；
@Override
public void remove(E element) {
int index = indexOf(element);
if (index != -1) {
remove(index);
}
}（4）移除对应角标处的元素
a、先将需要删除的元素单独获取出来。
b、根据在链表中删除位置的不同，做出相应的操作；
@Override
public E remove(int index) {
if (index < 0 || index >= size) {
throw new IllegalArgumentException("remove index out of range");
}
E ret = null;
if (size == 1) {
ret = head.data;
head = null;
tail = null;
} else if (index == 0) {
Node n = head;
ret = n.data;
head = n.next;
n.next = null;
} else if (index == size - 1) {
Node p = head;
while (p.next != tail) {
p = p.next;
}
ret = tail.data;
p.next = null;
tail = p;
} else {
Node p = head;
for (int i = 0; i < index - 1; i++) {
p = p.next;
}
Node n = p.next;
ret = n.data;
p.next = n.next;
n.next = null;
}
size--;
return ret;
}（5）获取相应角标处的元素
a、先对角标是否在链表中进行判断。
b、对在链表中不同位置处的元素获取进行相应操作。
@Override
public E get(int index) {
if (index < 0 || index >= size) {
throw new IllegalArgumentException("get index out of range");
}
if (index == 0) {
return head.data;
} else if (index == size - 1) {
return tail.data;
} else {
Node p = head;
for (int i = 0; i < index; i++) {
p = p.next;
}
return p.data;
}
}（6）修改对应角标处的元素
a、先对角标是否在链表中进行判断。
b、对在链表中不同位置处的元素修改进行相应操作。
@Override
public E set(int index, E element) {
if (index < 0 || index >= size) {
throw new IllegalArgumentException("get index out of range");
}
E ret = null;
if (index == 0) {
ret = head.data;
head.data = element;
} else if (index == size - 1) {
ret = tail.data;
tail.data = element;
} else {
Node p = head;
for (int i = 0; i < index; i++) {
p = p.next;
}
ret = p.data;
p.data = element;
}
return ret;
}
（7）获取链表中的元素个数
因底层用List实现，所以获取size 的方法和list的方法一致；
@Override
public int size() {
return size;
}（8）获取元素在链表中的角标
@Override
public int indexOf(E element) {
Node p = head;
int index = 0;
while (!p.data.equals(element)) {
p = p.next;
index++;
if (p == null) {
return -1;
}
}
return index;
}（9）判断是否包含此元素
@Override
public boolean contains(E element) {
return indexOf(element) != -1;
}（10）判断链表是否为空
@Override
public boolean isEmpty() {
return size == 0 && head == null && tail == null;
}（11）清空链表
@Override
public void clear() {
head = null;
tail = null;
size = 0;
}（12）toString()
a、判空操作，如果为空则返回[]
b、如果不为空，则将链表中的所有元素拼接在[]中输出
@Override
public String toString() {
StringBuilder sb = new StringBuilder();
sb.append('[');
if (isEmpty()) {
sb.append(']');
} else {
Node p = head;
while (true) {
sb.append(p.data);
if (p == tail) {
sb.append(']');
break;
}
sb.append(',');
sb.append(' ');
p = p.next;
}
}
return sb.toString();
}