Java链表入门(超详细)

2024-07-13 15:12| 来源: 网络整理| 查看: 265

Java链表入门超详细什么是链表创建链表1. 创建一个结点2. 插入一个结点-- 头插-- 尾插-- 指定位置插入 3.查找是否包含关键字key是否在单链表当中4.删除元素--删除第一次出现关键字为key的节点--删除所有值为key的节点 4.得到单链表的长度5.清空链表6.打印链表7.反转链表8.返回中间结点9.创建一个链表无头结点单向链表双向循环链表Java标准库中的链表LinkedList 和 ArrayList 的区别

什么是链表说起链表,可以说是让刚接触数据结构的同学非常懵逼的

那么什么是链表呢??

链表（Linked list）是一种常见的基础数据结构，是一种线性表，但是并不会按线性的顺序存储数据，而是在每一个节点里存到下一个节点的指针(Pointer)。

那么这是链表吗,是的,但是究竟是什么意思呢在这里插入图片描述

其实,链表就像是解密游戏一样,只有到达一个地点,才会有NPC给你下一个地点的地图,从而才能知道下个地点的位置所以链表也是一样,对于一个链表,一个结点除了要保存结点自身的值以外,还需要保存下一个结点的地址.

这是一个简单链表的单个结点,val代表当前结点存储的值,next是一个引用,指向下一个结点由于Java中不存在指针,所以结点通常为一个类,而next则是一个结点类实例的引用

可以看到,每一结点都保存了下一个节点的地址,所以,链表不要求每个结点中的地址空间连续

创建链表

–> 怎么创建一个链表呢 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; } //元素个数+1 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++; } – 指定位置插入

对于指定位置插入,需要用户数据需要插入的位置. 如须在上述链表中index = 2 的位置插入10,链表如下在这里插入图片描述 !!! : 第一个元素下标为 0

//任意位置插入,第一个数据节点为0号下标 public boolean addIndex(int index, int val) { //判断index是否合理 if(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) { //如果找到,返回true if (next.value == key) { return true; } next = next.next; } //未找到,返回 false return 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 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 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) { //如果找到,返回true if (next.value == key) { return true; } next = next.next; } //未找到,返回 false return 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 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 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)尾插 evoid add(int index, E element)将 e 插入到 index 位置boolean addAll(Collection

【本文地址】

公司简介

联系我们