开发语言 Java中的链表

文章目录

前言一、链表的概念及结构二、单向不带头非循坏链表的实现2.1打印链表2.2求链表的长度2.3头插法2.4尾插法2.5任意位置插入2.6查找是否包含某个元素的节点2.7删除第一次出现这个元素的节点2.8删除包含这个元素的所以节点2.9清空链表单向链表的测试

三、双向不带头非循坏链表的实现3.1打印双向链表3.2求双向链表的长度3.3头插法3.4尾插法3.5任意位置插入3.6查找是否包含某个元素的节点3.7删除第一次出现这个元素的节点3.7删除包含这个元素的所有节点3.9清空双向链表双向链表的测试LinkedList的遍历方式四、ArrayList和LinkedList的区别

前言

在前面我们已经学习了关于顺序表ArrayList的一些基本操作。通过源码知道，ArrayList底层使用数组来存储元素，由于其底层是一段连续空间，当在ArrayList任意位置插入或者删除元素时，就需要将后序元素整体往前或者往后搬移，时间复杂度为O(n)，效率比较低，因此ArrayList不适合做任意位置插入和删除比较多的场景。因此：java集合中又引入了LinkedList，即链表结构

一、链表的概念及结构

链表是一种物理存储结构上非连续存储结构，数据元素的逻辑顺序是通过链表中的引用链接次序实现的 注意： 1.链式结构在逻辑上是连续的，但是在物理上不一定连续 2.现实中的结点一般都是从堆上申请出来的 3.从堆上申请的空间，是按照一定的策略来分配的，两次申请的空间可能是连续，也可能不连续

链表的结构有8种样式： 单向带头循坏、单向带头非循坏、单向不带头循坏、单向不带头非循坏 双向带头循坏、双向带头非循坏、双向不带头循坏、双向不带头非循坏

这里我们主要学习以下两中结构： 单向不带头非循坏 LinkedList底层使用的就是双向不带头非循坏

二、单向不带头非循坏链表的实现

创建一个类：

public class MySingleList {

static class ListNode {

public int val;

public ListNode next;

public ListNode(int val) {

this.val = val;

}

}

//链表的头节点

public ListNode head;

}

2.1打印链表

不带参数的打印

public void display() {

ListNode cur = head;

if(cur != null) {//遍历完所以节点

System.out.print(cur.val+" ");

cur = cur.next;

}

System.out.println();

}

带参数的打印

public void display(ListNode newHead) {

ListNode cur = newHead;

if(cur != null) {

System.out.print(cur.val+" ");

cur = cur.next;

}

System.out.println();

}

2.2求链表的长度

public int size(){

ListNode cur = head;

int count = 0;

while (cur != null) {

count++;

cur = cur.next;

}

return count;

}

2.3头插法

public void addFirst(int data){

ListNode node = new ListNode(data);

node.next = head;

head = node;

}

2.4尾插法

public void addLast(int data){

ListNode node = new ListNode(data);

if(head == null) {

head = node;

}else {

ListNode cur = head;

while (cur.next != null) {//走到最后一个节点的位置

cur = cur.next;

}

cur.next = node;

}

}

2.5任意位置插入

在任意位置插入时我们要判断该位置是否合法，不合法的时候要抛一个异常

public void addIndex(int index,int data){

if(index < 0 || index > size()) {

throw new IndexException("index位置不合法："+index);

}

ListNode node = new ListNode(data);

if(head == null) {

head = node;

return;

}

if(index == 0) {

addFirst(data);

return;

}

if(index == size()) {

addLast(data);

return;

}

//中间插入

ListNode cur = serchIndex(index);

node.next = cur.next;

cur.next = node;

}

找要添加节点位置的前一个节点

public ListNode serchIndex(int index) {

ListNode cur = head;

int count = 0;

while (count != index-1) {

cur = cur.next;

count++;

}

return cur;

}

2.6查找是否包含某个元素的节点

遍历这个链表找是否与这个元素相同

public boolean contains(int key){

ListNode cur = head;

while (cur != null) {

if(cur.val == key) {

return true;

}

cur = cur.next;

}

return false;

}

2.7删除第一次出现这个元素的节点

public void remove(int key){

if(head == null) {

return;

}

if(head.val == key) {

head = head.next;

return;

}

ListNode cur = findKey(key);

if(cur == null) {

return;//没有要删除的元素

}

ListNode del = cur.next;

cur.next = del.next;

}

要删除节点的前一个节点

public ListNode findKey(int key) {

ListNode cur = head;

while (cur.next != null) {

if(cur.next.val == key) {

return cur;

}else {

cur = cur.next;

}

}

return null;

}

2.8删除包含这个元素的所以节点

public void removeAllKey(int key){

if(head == null) {

return;

}

ListNode prev = head;

ListNode cur = head.next;

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;

}

}

2.9清空链表

清空链表只需要把头节点置为空

public void clear() {

head = null;

}

单向链表的测试

public class Test {

public static void main(String[] args) {

MySingleList list = new MySingleList();

list.addLast(30);//尾插

list.addLast(20);

list.addLast(30);

list.addLast(40);

list.addLast(50);

list.addFirst(100);//头插

list.addIndex(2,15);//任意位置插入

list.display();

System.out.println("*****");

System.out.println(list.contains(20));//查看是否包含某个节点

System.out.println("*****");

System.out.println(list.size());//求链表长度

System.out.println("*****");

list.remove(30);//删除第一个出现的节点

list.display();

list.removeAllKey(30);//删除包含这个元素的所以节点

System.out.println("*****");

list.display();

System.out.println("*****");

list.clear();//清空链表

list.display();

}

}

三、双向不带头非循坏链表的实现

创建一个类：

static class ListNode {

public int val;

public ListNode next;

public ListNode prev;

public ListNode(int val) {

this.val = val;

}

}

public ListNode head;

public ListNode last;

}

3.1打印双向链表

public void display(){

ListNode cur = head;

while (cur != null) {

System.out.print(cur.val+" ");

cur = cur.next;

}

System.out.println();

}

3.2求双向链表的长度

public int size(){

int count = 0;

ListNode cur = head;

while (cur != null) {

count++;

cur = cur.next;

}

return count;

}

3.3头插法

public void addFist(int data) {

ListNode node = new ListNode(data);

if(head == null) {//一个节点都没有的情况

head = node;

last = node;

}else {

node.next = head;

head.prev = node;

head = node;

}

}

3.4尾插法

public void addLast(int data) {

ListNode node = new ListNode(data);

if(head == null) {//一个节点都没有的情况

head = node;

last = node;

}else {

last.next = node;

node.prev = last;

last = node;

}

}

3.5任意位置插入

这里的插入与单向链表一样也需要判断该位置的合法性，不合法时抛一个异常

public void addIndex(int index,int data) {

if(index < 0 || index > size()) {

throw new IndexException("双向链表中index的位置不合法："+index);

}

if(index == 0) {

addFist(data);

}

if(index == size()) {

addLast(data);

}

ListNode cur = findIndex(index);

ListNode node = new ListNode(data);

node.next = cur;

cur.prev.next = node;

node.prev = cur.prev;

cur.prev = node;

}

要添加节点的位置

public ListNode findIndex(int index) {

ListNode cur = head;

if(index != 0) {

cur = cur.next;

index --;

}

return cur;

}

3.6查找是否包含某个元素的节点

public boolean contains(int key){

ListNode cur = head;

while (cur != null) {

if(cur.val == key) {

return true;

}

cur = cur.next;

}

return false;

}

3.7删除第一次出现这个元素的节点

因为数据结构是一门逻辑性非常严谨的学科，所以这里的删除需要考虑多种因素

public void remove(int key){

ListNode cur = head;

while (cur != null) {

if(cur.val == key) {

if(cur == head) {

head = head.next;

if (head != null) {

head.prev = null;

}else {

//只有一个节点，而且是需要删除的节点

last = null;

}

}else {

//删除中间节点

if(cur.next != null) {

cur.next.prev = cur.prev;

cur.prev.next = cur.next;

}else {

//删除尾巴节点

cur.prev.next = cur.next;

last = last.prev;

}

}

return;

}

cur = cur.next;

}

}

3.7删除包含这个元素的所有节点

public void remove(int key){

ListNode cur = head;

while (cur != null) {

if(cur.val == key) {

if(cur == head) {

head = head.next;

if (head != null) {

head.prev = null;

}else {

//只有一个节点，而且是需要删除的节点

last = null;

}

}else {

//删除中间节点

if(cur.next != null) {

cur.next.prev = cur.prev;

cur.prev.next = cur.next;

}else {

//删除尾巴节点

cur.prev.next = cur.next;

last = last.prev;

}

}

}

cur = cur.next;

}

}

3.9清空双向链表

public void clear(){

ListNode cur = head;

while (cur != null) {

ListNode curNext = cur.next;

cur.prev = null;

cur.next = null;

cur = cur.next;

}

head = null;//头节点置空

last = null;//尾巴节点置空

}

双向链表的测试

public class Test {

public static void main(String[] args) {

MyLinkedList myLinkedList = new MyLinkedList();

myLinkedList.addLast(12);//尾插法

myLinkedList.addLast(45);

myLinkedList.addLast(34);

myLinkedList.addLast(45);

myLinkedList.addFist(56);//头插法

myLinkedList.addIndex(2,15);//任意位置插入

myLinkedList.display();

System.out.println(myLinkedList.size());//求双向链表的长度

System.out.println("******");

System.out.println(myLinkedList.contains(23));//查找是否包含某个元素的节点

System.out.println("******");

myLinkedList.remove(45);//删除第一次出现这个元素的节点

myLinkedList.display();

System.out.println("******");

myLinkedList.removeAllKey(45);//删除包含这个元素的所以节点

myLinkedList.display();

System.out.println("******");

myLinkedList.clear();//清空链表

myLinkedList.display();

}

}

LinkedList的遍历方式

关于LinkedList的遍历方式有四种：

public class Test {

public static void main(String[] args) {

LinkedList list = new LinkedList<>();

list.add(1);

list.add(2);

list.add(3);

list.add(4);

System.out.println(list);

//for循坏遍历

for (int i = 0; i < list.size(); i++) {

System.out.print(list.get(i)+" ");

}

System.out.println();

System.out.println("*******");

//foreach遍历

for (int m : list) {

System.out.print(m +" ");

}

System.out.println();

System.out.println("*******");

//使用迭代器——正向遍历

ListIterator it = list.listIterator();

while (it.hasNext()) {

System.out.print(it.next()+" ");

}

System.out.println();

System.out.println("*******");

//使用迭代器——反向遍历

ListIterator it2 = list.listIterator(list.size());

while (it2.hasPrevious()) {

System.out.print(it2.previous()+" ");

}

System.out.println();

}

}

四、ArrayList和LinkedList的区别

1.ArrayList在物理上是连续的，LinkedList在逻辑上连续，但在物理上不一定连续 2.ArrayList和LinkedList是两种不同的数据结构。ArrayList是基于动态数组的，而LinkedList则是基于链表的 3.当需要随机访问元素（如get和set操作）时，ArrayList效率更高，因为LinkedList需要逐个查找。但当进行数据的增加和删除操作（如add和remove操作）时，LinkedList效率更高，因为ArrayList在进行这些操作时需要移动大量数据 4.ArrayList需要手动设置固定大小的容量，使用方便但自由性低；而LinkedList能够随数据量变化而动态调整，自由性较高但使用较为复杂

参考文章

 您阅读本篇文章共花了：