Java链表入门 超详细
- 什么是链表
- 创建链表
- 1. 创建一个结点
- 2. 插入一个结点
- — 头插
- — 尾插
- — 指定位置插入
- 3.查找是否包含关键字key是否在单链表当中
- 4.删除元素
- –删除第一次出现关键字为key的节点
- –删除所有值为key的节点
- 4.得到单链表的长度
- 5.清空链表
- 6.打印链表
- 7.反转链表
- 8.返回中间结点
- 9.创建一个链表
- 无头结点单向链表
- 双向循环链表
- Java标准库中的链表
- LinkedList 和 ArrayList 的区别
什么是链表
说起链表,可以说是让刚接触数据结构的同学非常懵逼的
那么什么是链表呢” />
其实,链表就像是解密游戏一样,只有到达一个地点,才会有NPC给你下一个地点的地图,从而才能知道下个地点的位置
所以链表也是一样,对于一个链表,一个结点除了要保存结点自身的值以外,还需要保存下一个结点的地址.
这是一个简单链表的单个结点,val代表当前结点存储的值,next是一个引用,指向下一个结点
由于Java中不存在指针,所以结点通常为一个类,而next则是一个结点类实例的引用
可以看到,每一结点都保存了下一个节点的地址,所以,链表不要求每个结点中的地址空间连续
创建链表
–> 怎么创建一个链表呢 <–
1. 创建一个结点
上面说到,链表是由一个一个的结点组成,后一个结点依靠前一个才能找到,那么如何构造结点呢” />//结点类采用内部类private static class Node{//值public int value;// Node 节点类型,引用当前结点的下一个结点public Node next; //构造方法初始化/** * @param value 值 */public Node(int value){this.value = value;next = null;}}
节点创建完毕,那么,链表究竟有些什么操作呢?
//头插法public void addFirst(int value){}//尾插法public void addLast(int value){}//任意位置插入,第一个数据节点为0号下标public boolean addIndex(int index,int value){return false;}//查找是否包含关键字key是否在单链表当中public boolean contains(int key){return false;}//删除第一次出现关键字为key的节点public void remove(int key){}//删除所有值为key的节点public void removeAllKey(int key){}//得到单链表的长度public int size(){return -1;}public void display(){}public void clear(){}太多了吧!!!
接下来,一起欣赏每个方法具体如何实现
再此之前,我们要先创建一个链表,此处采用手工创建方法,具体方法后面演示.
public void createLinkedList(){Node node = new Node(0);Node node1 = new Node(1);Node node2 = new Node(2);Node node3 = new Node(3);Node node4 = new Node(4);//创建一个链表head = node;node.next = node1;node1.next= node2;node2.next = node3;node3.next = node4;}2. 插入一个结点
插入一个结点的方式一般有三种,一种头插法,一种尾插法,最后一种指定位置加入元素
头插法 : 在链表的起始位置加入一个元素
尾插法 : 在链表的末尾位置加入一个元素
指定位置插入 : 调用方法时传入index下表,将要加入的元素插入到下标位置– 头插
由上述代码创建的链表就长这个样子啦
插入一个元素6,就变成如下模样~~
那么,代码呢!!//头插法public void addFirst(int val) {//根据值创建新结点Node node = new Node(val);//判断链表是否为空if(size == 0){this.head = node;}else {//链表不为空node.next = head;head = node;}//元素个数+1this.size++;}– 尾插
和头插法相似,插入后的链表长这个样子
注意:因为这是单向链表,所以,要想插入到最后一个位置,需要遍历链表.
具体代码如下//尾插法public void addLast(int val) {//根据值创建新结点Node node = new Node(val);//判断链表是否为空if (size == 0) {this.head = node;} else {//链表不为空//创建临时变量记录头结点,防止遍历后找不到头结点Node tmpHead = head;Node cur = tmpHead.next;while (cur != null) {tmpHead = cur;cur = cur.next;}// 循环结束后,tmpHead为最后一个结点tmpHead.next = node;}this.size++;}– 指定位置插入
对于指定位置插入,需要用户数据需要插入的位置.
如须在上述链表中index = 2 的位置插入10,链表如下
!!! : 第一个元素下标为 0//任意位置插入,第一个数据节点为0号下标public boolean addIndex(int index, int val) {//判断index是否合理if(index < 0 || index > this.size){System.out.println("输入下标不合理...");return false;}Node node = new Node(val);Node tmpHead = this.head;//如果index为0进行头插if(index == 0){node.next = head;head = node;return true;}//循环结束后,tmpHead 在待插入位置的前一个位置while (index > 1){tmpHead = tmpHead.next;index--;}node.next = tmpHead.next;tmpHead.next = node;this.size++;return true;}插入操作到此结束
3.查找是否包含关键字key是否在单链表当中
遍历链表,按个查找即可
//查找是否包含关键字key是否在单链表当中public boolean contains(int key) {//记录头结点Node next = this.head;//遍历每一个结点while (next != null) {//如果找到,返回trueif (next.value == key) {return true;}next = next.next;}//未找到,返回 falsereturn false;}4.删除元素
–删除第一次出现关键字为key的节点
关键之处在于
node = next;
next = next.next;//删除第一次出现关键字为key的节点public void remove(int key) {if (!contains(key)) {System.out.println("没有该元素");}Node next = this.head;Node node = next;//判断第一个元素if (next.value == key) {this.head = next.next;next.next = null;this.size--;return;}//循环判断后续元素while (next != null) {if (next.value == key) {//跳过中间元素node.next = next.next;//置空next.next = null;//元素减一this.size--;return;}//让 next 始终在 node 的下一个元素node = next;next = next.next;}}–删除所有值为key的节点
与删除一个元素不同的是,删除所有key值元素在循环判断时找到指定元素时不退出,继续进行查找,直到链表遍历完成.
//删除所有值为key的节点public void removeAllKey(int key) {if (this.head == null) {return;}Node cur = this.head.next;Node pre = this.head;//遍历整个链表,判断每个元素while (cur != null) {if (cur.value == key) {// 跳过 指定元素pre.next = cur.next;} else {pre = cur;}cur = cur.next;}/*Node cur = this.head.next;Node pre = this.head;上述代码跳过了head.value所以需要单独判断*/if (this.head.value == key) {this.head = this.head.next;}}4.得到单链表的长度
//得到单链表的长度 public int size() {return this.size;}5.清空链表
直接使用
this.head = null;可以达到一样的效果,但此处对每个结点引用置空.public void clear() {this.size = 0;Node tmp;while (head.next != null) {tmp = this.head.next;//置空head.next = null;head = tmp;}this.head = null;}6.打印链表
//打印链表public void display() {Node tmp = this.head;System.out.print("[");while (tmp != null) {if (tmp.next == null) System.out.print(tmp.value);else System.out.print(tmp.value + ",");tmp = tmp.next;}System.out.println("]");}7.反转链表
反转链表的核心在于,需要一个pre记录下一个结点是否为空,因为在程序运行过程中,cur会断开与下一个节点的连接,所以需要单独添加引用记录.
//反转链表public Node reverse() {if (this.size == 0) {return null;}if (head.next == null) {return head;}Node cur = head.next;head.next = null;//pre记录下一个元素Node pre;while (cur != null) {pre = cur.next;cur.next = head;head = cur;cur = pre;}return head;}8.返回中间结点
采用快慢指针的思想,慢指针一次移动一步,快指针一次移动2步,当快指针移动到链表末尾时,慢指针就在链表中间位置
//返回中间结点public Node middleNode() {Node fast = head;Node slow = head;while(fast != null && fast.next != null){fast = fast.next.next;slow = slow.next;}return slow;}9.创建一个链表
传入一个数组快速创建一个链表,实际中,根据情况做判断.
//创建一个链表public void create(int[] arr){if(this.head != null){System.out.println("链表不为空!");}Node tmp = null;for (int i = 0; i < arr.length; i++) {Node node = new Node(arr[i]);if(this.head == null){this.head = node;tmp = this.head;}tmp.next = node;tmp = tmp.next;}this.size = arr.length;}到这里为止,关于链表的基本操作就结束了…
下面是整个源码.
对于链表,以上演示的是无头单向不循环链表,对应的还有很多的不同实现的链表,如,有头双向循环链表
对于循环链表,就是每一个结点都记录了前后2个节点的引用,
对于双向链表,就是除了头结点外,还记录了尾节点.无头结点单向链表
//无头结点单向链表public class LinkedList {//结点类private static class Node {public int value;public Node next;public Node(int value) {this.value = value;next = null;}}//指定头结点为空private Node head = null;private int size = 0;public void createLinkedList() {Node node = new Node(0);Node node1 = new Node(1);Node node2 = new Node(2);Node node3 = new Node(3);Node node4 = new Node(4);//创建一个链表head = node;node.next = node1;node1.next = node2;node2.next = node3;node3.next = node4;size = 5;}//头插法public void addFirst(int val) {//根据值创建新结点Node node = new Node(val);//判断链表是否为空if (size == 0) {this.head = node;} else {//链表不为空node.next = head;head = node;}this.size++;}//尾插法public void addLast(int val) {//根据值创建新结点Node node = new Node(val);//判断链表是否为空if (size == 0) {this.head = node;} else {//链表不为空//创建临时变量记录头结点,防止遍历后找不到头结点Node tmpHead = head;Node cur = tmpHead.next;while (cur != null) {tmpHead = cur;cur = cur.next;}// 循环结束后,tmpHead为最后一个结点tmpHead.next = node;}this.size++;}//任意位置插入,第一个数据节点为0号下标public boolean addIndex(int index, int val) {//判断index是否合理if (index < 0 || index > this.size) {System.out.println("输入下标不合理...");return false;}Node node = new Node(val);Node tmpHead = this.head;//如果index为0进行头插if (index == 0) {node.next = head;head = node;return true;}//循环结束后,tmpHead 在待插入位置的前一个位置while (index > 1) {tmpHead = tmpHead.next;index--;}node.next = tmpHead.next;tmpHead.next = node;this.size++;return true;}//查找是否包含关键字key是否在单链表当中public boolean contains(int key) {//记录头结点Node next = this.head;//遍历每一个结点while (next != null) {//如果找到,返回trueif (next.value == key) {return true;}next = next.next;}//未找到,返回 falsereturn false;}//删除第一次出现关键字为key的节点public void remove(int key) {if (!contains(key)) {System.out.println("没有该元素");}Node next = this.head;Node node = next;//判断第一个元素if (next.value == key) {this.head = next.next;next.next = null;this.size--;return;}//循环判断后续元素while (next != null) {if (next.value == key) {//跳过中间元素node.next = next.next;//置空next.next = null;//元素减一this.size--;return;}//让 next 始终在 node 的下一个元素node = next;next = next.next;}}//删除所有值为key的节点public void removeAllKey(int key) {if (this.head == null) {return;}Node cur = this.head.next;Node pre = this.head;//遍历整个链表,判断每个元素while (cur != null) {if (cur.value == key) {// 跳过 指定元素pre.next = cur.next;} else {pre = cur;}cur = cur.next;}/*Node cur = this.head.next;Node pre = this.head;上述代码跳过了head.value所以需要单独判断*/if (this.head.value == key) {this.head = this.head.next;}}//得到单链表的长度public int size() {return this.size;}//打印链表public void display() {Node tmp = this.head;System.out.print("[");while (tmp != null) {if (tmp.next == null) System.out.print(tmp.value);else System.out.print(tmp.value + ",");tmp = tmp.next;}System.out.println("]");}//清空链表public void clear() {this.size = 0;Node tmp;while (head.next != null) {tmp = this.head.next;head.next = null;head = tmp;}this.head = null;}//反转链表public Node reverse() {if (this.size == 0) {return null;}if (head.next == null) {return head;}Node cur = head.next;head.next = null;//pre记录下一个元素Node pre;while (cur != null) {pre = cur.next;cur.next = head;head = cur;cur = pre;}return head;}//返回中间结点public Node middleNode() {Node fast = head;Node slow = head;while(fast != null && fast.next != null){fast = fast.next.next;slow = slow.next;}return slow;}public void create(int[] arr){if(this.head != null){System.out.println("链表不为空!");}Node tmp = null;for (int i = 0; i < arr.length; i++) {Node node = new Node(arr[i]);if(this.head == null){this.head = node;tmp = this.head;}assert tmp != null;tmp.next = node;tmp = tmp.next;}this.size = arr.length;}}双向循环链表
public class MyDoubleLinkedList {static private class Node {public int val;//记录前一个结点public Node pre;//记录后一个结点public Node next;public Node(int val) {this.val = val;this.pre = null;this.next = null;}}//记录头结点private Node head;//记录尾结点private Node last;//头插法public void addFirst(int val) {Node tmp = new Node(val);if (head == null) {head = tmp;last = head;} else {tmp.next = head;head.pre = tmp;head = tmp;}}//尾插法public void addLast(int val) {Node tmp = new Node(val);if (head == null) {head = tmp;last = head;} else {last.next = tmp;tmp.pre = last;last = tmp;}}//任意位置插入,第一个数据节点为0号下标public void addIndex(int index, int val) {if (index < 0 || index > size()) {System.out.println("下标越界");}Node tmp = new Node(val);Node next = head;if(head == null){head = tmp;last = tmp;return;}if (index == 0) {tmp.next = head;head.pre = tmp;head = tmp;return;}if (index == size()) {last.next = tmp;tmp.pre = last;last = tmp;return;}while (index > 0) {next = next.next;index--;}next.pre.next = tmp;tmp.next = next;tmp.pre = next.pre;next.pre = tmp;}//查找是否包含关键字key是否在单链表当中public boolean contains(int key) {Node next = head;while (next != null) {if (next.val == key) {return true;}next = next.next;}return false;}//删除第一次出现关键字为key的节点public boolean remove(int key) {if(head == null || head.next == null){head = null;return true;}if(head.val == key){head = head.next;head.pre = null;return true;}Node tmp = head;while (tmp.val != key){tmp = tmp.next;if(tmp == null){return false;}}if(tmp == last){last.pre.next = null;return true;}tmp.pre.next = tmp.next;tmp.next.pre = tmp.pre;return true;}//删除所有值为key的节点public void removeAllKey(int key) {boolean b = true;while (b){b = false;boolean remove = remove(key);if(remove) b = true;}}//得到单链表的长度public int size() {int size = 0;Node next = head;while (next != null) {next = next.next;size++;}return size;}public void display() {Node next = head;System.out.print("[");while (next != null) {System.out.print(next.val + " ");next = next.next;}System.out.println("]");}public void clear() {while (head.next != null){head = head.next;head.pre = null;}head = null;last = null;}}Java标准库中的链表
在Java标准库中,内置了一个双向链表LinkedList类
方法 解释 boolean add(E e) 尾插 e void add(int index, E element) 将 e 插入到 index 位置 boolean addAll(Collectionpublic static void main(String[] args) {LinkedList<Integer> list = new LinkedList<>();list.add(1); // add(elem): 表示尾插list.add(2);list.add(3);list.add(4);list.add(5);list.add(6);list.add(7);System.out.println(list.size());System.out.println(list);// 在起始位置插入0list.add(0, 0); // add(index, elem): 在index位置插入元素elemSystem.out.println(list);list.remove(); // remove(): 删除第一个元素，内部调用的是removeFirst()list.removeFirst(); // removeFirst(): 删除第一个元素list.removeLast(); // removeLast(): 删除最后元素list.remove(1); // remove(index): 删除index位置的元素System.out.println(list);// contains(elem): 检测elem元素是否存在，如果存在返回true，否则返回falseif(!list.contains(1)){list.add(0, 1);}list.add(1);System.out.println(list);System.out.println(list.indexOf(1)); // indexOf(elem): 从前往后找到第一个elem的位置System.out.println(list.lastIndexOf(1)); // lastIndexOf(elem): 从后往前找第一个1的位置int elem = list.get(0); // get(index): 获取指定位置元素list.set(0, 100); // set(index, elem): 将index位置的元素设置为elemSystem.out.println(list);// subList(from, to): 用list中[from, to)之间的元素构造一个新的LinkedList返回List<Integer> copy = list.subList(0, 3); System.out.println(list);System.out.println(copy);list.clear(); // 将list中元素清空System.out.println(list.size());} 运行结果
LinkedList 和 ArrayList 的区别
不同点 ArrayList LinkedList 存储空间上 物理上一定连续 逻辑上连续，但物理上不一定连续 随机访问 支持O(1) 不支持：O(N) 头插 需要搬移元素，效率低O(N) 只需修改引用的指向，时间复杂度为O(1) 插入 空间不够时需要扩容 没有容量的概念 应用场景 元素高效存储+频繁访问 任意位置插入和删除频繁 第一次发博客,希望大家多多支持
新人博主水平有限,如有不足,多多指正.
