一.链表的概念及结构

链表是一种物理存储结构上非连续存储结构，数据元素的逻辑顺序是通过链表中的引用链接次序实现的。

value存数据，节点存下一个的地址，通过节点找下一个数据，每个节点都是一个对象

注意：

链式结构在逻辑上是连续的，但在物理上不一定连续】

现实中的节点一般都是从堆上申请出来的

从堆上申请的空间，是按照一定的策略来分配的，两次申请的空间可能连续，也可能不连续

链0pooooooooooooooooooo表有非常多种，以下情况组合起来就有八种链表结构

1.单向或双向

2.带头或不带头

3.循环或非循环

我们重点掌握两种

1.无头单向非循环列表：结构简单，一般不用来单独存数据，更多是作为其他数据结构的子结构，如哈希桶，图的邻接表等等

2.无头双向链表：在Java的框架中，LinkedList底层实现就是无头双向循环链表

二.链表的实现

1.简单创建

public class MySingleList {static class ListNode {public int val;//节点的值域public ListNode next;//下一个节点的地址public ListNode(int val) {this.val = val;}}public ListNode head;//表示当前链表的头节点public void createList() {ListNode node1 = new ListNode(12);ListNode node2 = new ListNode(23);ListNode node3 = new ListNode(34);ListNode node4 = new ListNode(45);ListNode node5 = new ListNode(56);node1.next = node2;node2.next = node3;node3.next = node4;node4.next = node5;this.head = node1;}
}

2.遍历链表

 public void display() {ListNode cur = head;while (cur != null) {System.out.print(cur.val+" ");cur = cur.next;}System.out.println();}

注意head不能丢

3.得到单链表的长度

public int size(){int count = 0;ListNode cur = head;while (cur != null) {count++;cur = cur.next;}return count;}

4.查找关键字key是否在单链表中

  public boolean contains(int key){ListNode cur = head;while (cur != null) {if(cur.val == key) {return true;}cur = cur.next;}return false;}

5.头插法

 public void addFirst(int data){ListNode node = new ListNode(data);node.next = head;head = node;}

6.尾插法

 public void addLast(int data){ListNode node = new ListNode(data);ListNode cur = head;if(cur == null) {head = node;return;}//找到链表的尾巴  注意是cur.next 不是curwhile (cur.next != null) {cur = cur.next;}cur.next = node;}

7.任意位置插入，第一个数据节点为0号下标

   public void addIndex(int index,int data){if(index < 0 || index > size()) {System.out.println("index 不合法");return;}if(index == 0) {addFirst(data);return;}if(index == size()) {addLast(data);return;}ListNode cur = findIndexSubOne(index);ListNode node = new ListNode(data);node.next = cur.next;cur.next = node;}/*** 找到要删除节点位置的前一个节点* @param index* @return*/private ListNode findIndexSubOne(int index) {ListNode cur = head;while (index-1 != 0) {cur = cur.next;index--;}return cur;}

8.删除第一次出现关键字为key的节点

 public void remove(int key){if(head == null) {return;}//单独删除头节点if(head.val == key) {head = head.next;return;}ListNode cur = searchPrev(key);if(cur == null) {System.out.println("没有你要删除的数字");return;}ListNode del = cur.next;cur.next = del.next;}/*** 找到关键字 key的前驱* @param key* @return*/private ListNode searchPrev(int key) {ListNode cur = head;while (cur.next != null) {if(cur.next.val == key) {return cur;}cur = cur.next;}return null;}

9.删除所有值为key的节点

 public void removeAllKey(int key){if(head == null) {return;}ListNode cur = head.next;ListNode prev = head;while (cur != null) {if(cur.val == key) {prev.next = cur.next;cur = cur.next;}else {prev = cur;cur = cur.next;}}if(head.val == key) {head = head.next;}}

10.清空链表

    public void clear() {this.head = null;}