文章目录
- 1. 链表
- 1.1
- 1.2 链表的概念及其结构
- 1.3 自己实现一个链表
1. 链表
1.1
之前我们学习了 顺序表ArrayList，并自己实现了 ArrayList ，发现它在删除元素和添加元素时很麻烦，最坏的情况时，需要将所有的元素移动，因此在插入和删除较多的情况下使用 ArrayList 很麻烦，于是 Java 则引入了链表 LinkedList
1.2 链表的概念及其结构
之前学过的顺序表在物理上连续（内存），逻辑上也是连续的；
而链表在物理上不一定连续，在逻辑上是连续的。
这就是一个结点，data 存储数据，next 存储下一个结点的地址。
由一个一个结点组织起来的就是链表。
链表的结构不止这一种，总共有八种。
- 带头结点的 和不带头结点的
- 单向 和 双向
- 循环 和 非循环
这三个组合起来共八种
什么！八种
但其实就学两个，吓死你
1.3 自己实现一个链表
- 打印链表
//打印链表public void display(){ListNode cur = head;while(cur != null){System.out.print(cur.value + " ");cur = cur.next;}System.out.println();}
- 获取链表长度
//获取链表长度public int size(){ListNode cur = head;int count = 0;while(cur != null){count++;cur = cur.next;}return count;}
- 头插法
头插法就是将当前结点插入到链表最前面的位置
//头插法public void addFirst(int value){ListNode node = new ListNode(value);node.next = head;head = node;}
- 尾插法
尾插法就是将当前结点插入到最后面的位置
//尾插法public void addLast(int value){ListNode node = new ListNode(value);ListNode cur = head;if(head == null){head = node;return;}while(cur.next != null){cur = cur.next;}cur.next = node;}
- 任意位置插入
public class IndexNotLegalException extends RuntimeException{public IndexNotLegalException(){}public IndexNotLegalException(String msg){super(msg);}}//任意位置插入public void addIndex(int index,int value){ListNode node = new ListNode(value);ListNode cur = head;try{checkIndex(index);}catch (IndexNotLegalException e){e.printStackTrace();}if(index == 0){addFirst(value);return;}if(index == size()){addLast(value);return;}for(int i = 0; i < index;i++){cur = cur.next;}node.next = cur.next;cur.next = node;}public void checkIndex(int index){if(index < 0 || index > size()){throw new IndexNotLegalException("index不合法");}}
- 查找链表是否包含关键字 key
//查找链表是否包含关键字keypublic boolean contain(int key){ListNode cur = head;while(cur != null){if(cur.value == key){return true;}cur = cur.next;}return false;}
- 删除第一次出现关键字为key的节点
//删除第一次出现关键字为key的节点public void remove(int key){ListNode cur = head;if(contain(key)){if(head.value == key){head = head.next;return;}while(cur.next != null){if(cur.next.value == key){cur.next = cur.next.next;return;}cur = cur.next;}}else {System.out.println("没有找到该结点");}}
- 删除所有值为key的节点
//删除所有值为key的节点public void removeAllKey(int key){if(head == null){return;}ListNode prev = head;ListNode cur = prev.next;while(cur != null){if(cur.value == key){prev.next = cur.next;cur = cur.next;}else{prev = cur;cur = cur.next;}}if(head.value == key){head = head.next;}}
- 清空链表
//清空链表public void clear(){head = null;}
这次的图画的完美多了
完整代码（测试类自己写哦）
public class MySingleLinkedList {//内部类class ListNode{public int value;public ListNode next;public ListNode(int value) {this.value = value;}}//代表链表的头结点public ListNode head;//创建链表public void createList(){ListNode node1 = new ListNode(12);ListNode node2 = new ListNode(15);ListNode node3 = new ListNode(28);ListNode node4 = new ListNode(47);ListNode node5 = new ListNode(50);node1.next = node2;node2.next = node3;node3.next = node4;node4.next = node5;this.head = node1;}//打印链表public void display(){ListNode cur = head;while(cur != null){System.out.print(cur.value + " ");cur = cur.next;}System.out.println();}//获取链表长度public int size(){ListNode cur = head;int count = 0;while(cur != null){count++;cur = cur.next;}return count;}//头插法public void addFirst(int value){ListNode node = new ListNode(value);node.next = head;head = node;}//尾插法public void addLast(int value){ListNode node = new ListNode(value);ListNode cur = head;if(head == null){head = node;return;}while(cur.next != null){cur = cur.next;}cur.next = node;}//任意位置插入public void addIndex(int index,int value){ListNode node = new ListNode(value);ListNode cur = head;try{checkIndex(index);}catch (IndexNotLegalException e){e.printStackTrace();}if(index == 0){addFirst(value);return;}if(index == size()){addLast(value);return;}for(int i = 0; i < index;i++){cur = cur.next;}node.next = cur.next;cur.next = node;}public void checkIndex(int index){if(index < 0 || index > size()){throw new IndexNotLegalException("index不合法");}}//查找链表是否包含关键字keypublic boolean contain(int key){ListNode cur = head;while(cur != null){if(cur.value == key){return true;}cur = cur.next;}return false;}//删除第一次出现关键字为key的节点public void remove(int key){ListNode cur = head;if(contain(key)){if(head.value == key){head = head.next;return;}while(cur.next != null){if(cur.next.value == key){cur.next = cur.next.next;return;}cur = cur.next;}}else {System.out.println("没有找到该结点");}}//删除所有值为key的节点public void removeAllKey(int key){if(head == null){return;}ListNode prev = head;ListNode cur = prev.next;while(cur != null){if(cur.value == key){prev.next = cur.next;cur = cur.next;}else{prev = cur;cur = cur.next;}}if(head.value == key){head = head.next;}}//清空链表public void clear(){head = null;}
}
public class IndexNotLegalException extends RuntimeException{public IndexNotLegalException(){}public IndexNotLegalException(String msg){super(msg);}}终于完事了，我要好好躺着了
