1.链表概念
链表：
- 链表是一种递归的数据结构，
- 由许多个结点（node）组成，每个节点含有一个泛型的元素和指向另一个链表的引用
- 链表可以为空
结点:
class Node{
Item item;
Node next;
}
构造一个链表:
构造一些结点，将第一个结点中的引用指向第二个结点，将第二个结点中的引用指向第三个结点，。。。循环下去就得到一个多结点链表；
Node first = new Node();
Node second = new Node();
Node third = new Node();
...
first.next = second;
second.next = third
...
数组的缺点：
- 需要在使用前知道数组的长度；
- 需要大块连续的内存
- 插入删除元素的效率低、速度慢
- 空间通常有限制的
链表：离散型数据结构，由于是通过引用指向下一个结点，所以在内存中各节点的顺序不必连续；
相对于内存连续型容器（如数组）的优缺点：
- 优势：增删元素速度快，插入和删除元素仅需要改动变动元素的引用即可，
- 劣势：查找慢，内存不连续，故需要从第一个结点开始遍历，比如要查找第五个元素，则需要从第一个结点开始遍历
链表种类(3种)：
-
单链表：
-
双链表：
-
循环链表：
- 循环单链表
- 循环双链表
2.链表操作
链表的核心操作包括：插入、删除、查找(遍历)
2.1链表的插入、删除
-
在表头插入、删除
插入：只需将要插入的结点指向原链表的第一个结点即可；
Node newFirst = new Node();
newFirst.next = oldFirst;
删除：删除表头只需要将首结点指向为下一个结点即可；
first = first.next
-
在表尾插入、删除
插入：只需要将原链表中尾结点重新指向要插入的结点即可
Node newEnd = new Node(); oldEnd.next = newEnd;删除：删除表尾的结点，需要找到倒数第二个结点，将该结点指向null；
-
在其他位置插入、删除:
2.2遍历
遍历数组：
for（int i= 0； i < arr.length; i++）{
// arr[i]
}
遍历链表：
for (Node node = first; node != null; ndoe = ndoe.next){
// node.term
}
单链表操作：
2.3 实现代码
以下用单链表实现对链表的增删操作：
public class SingleLinkedList<T> {
private Integer size = 0;
private Node head;
/**
* 将结点添加到末尾
* @param element 要添加的元素
* @return 是否添加成功
*/
public boolean add(T element){
Node node = new Node(element);
if (head == null) {
head = node;
} else {
Node tmp = head;
while (tmp.next != null) {
tmp = tmp.next;
}
tmp.next = node;
}
size++;
return true;
}
/**
* 将元素插入指定指定的下标位置
* @param index 插入的下标
* @param element 插入的元素
* @return 是否添加成功
*/
public boolean add(int index, T element){
if(index >= size || index < 0){ //异常下标
throw new IndexOutOfBoundsException("size:" + size + " index: " + index );
}
Node newNode = new Node(element);
if (index == 0){ //插入到表头的位置
newNode.next = head;
head = newNode;
} else {
Node tmp = head;
for (int i = 0; i < index - 1; i++) {
tmp = tmp.next;
}
newNode.next = tmp.next;
tmp.next = newNode;
}
size++;
return true;
}
/**
* 默认删除链表最后一个结点, 并返回值
*/
public T remove(){
if (head == null) {//空链表
throw new RuntimeException("链表为空！无法删除！");
}
if (size < 2) {//单元素链表
T tmp = head.item;
head = null;
size--;
return tmp;
}
Node tmp = head;
while (tmp.next.next != null){
tmp = tmp.next;
}
T returnVal = tmp.next.item;
tmp.next = null;
size--;
return returnVal;
}
/**
* 删除指定下标的结点
* @param index 要删除的结点下标
* @return 返回已经删除元素
*/
public T remove(Integer index){
if (head == null) {
throw new RuntimeException("链表为空！无法删除！");
}
if(index >= size || index < 0) {
throw new IndexOutOfBoundsException("size: " + size + " index: " + index);
}
Node tmp = head;
for (int i = 0; i < index - 1; i++) {
tmp = tmp.next;
}
Node returnNode = tmp.next; //即将删除的结点
tmp.next = tmp.next.next;
returnNode.next = null;
return returnNode.item;
}
/**
* 遍历打印链表
*/
public void print(){
Node tmp = head;
while (tmp != null){
System.out.print(tmp.item + " ");
tmp = tmp.next;
}
}
/**
* 内部类：结点
*/
class Node {
T item;
Node next;
public Node(T item) {
this.item = item;
}
public T getItem() {
return item;
}
public void setItem(T item) {
this.item = item;
}
public Node getNext() {
return next;
}
public void setNext(Node next) {
this.next = next;
}
}
public Integer getSize() {
return size;
}
public Node getHead() {
return head;
}
public void setHead(Node head) {
this.head = head;
}
}
测试一下单链表：
public class SingleLinkedListTest {
public static void main(String[] args) {
SingleLinkedList<String> singleLinkedList = new SingleLinkedList();
// 添加元素
System.out.println("---------添加元素--------");
singleLinkedList.add("a");
singleLinkedList.add("b");
singleLinkedList.add("c");
singleLinkedList.add("d");
singleLinkedList.add("e");
singleLinkedList.add("f");
singleLinkedList.print();
// 添加到指定位置
singleLinkedList.add(5, "h");
System.out.println();
singleLinkedList.print();
//删除最后一个元素
singleLinkedList.remove();
System.out.println();
System.out.println("---------删除元素--------");
singleLinkedList.print();
//删除指定元素
System.out.println();
singleLinkedList.remove(2);
singleLinkedList.print();
}
}
