我要评论目录
1.前言
在上一篇文章中，我们讲到arraylist不适合做任意位置插入和删除比较多的场景,因此java集合中又引入了linkedlist，即链表结构，通过链表来处理上述场景的问题。
2.链表
2.1链表的概念及结构
链表是一种物理存储结构上非连续存储结构，数据元素的逻辑顺序是通过链表中的引用链接次序实现的 。
linkedlist = linked + list = 链表 + 列表 = 链表列表
实际中链表的结构非常多样，以下情况组合起来就有8种链表结构：
1. 单向或者双向
2. 带头或者不带头
3. 循环或者非循环
虽然有这么多的链表的结构，但我们主要掌握以下两种:
- 无头单向非循环链表：结构简单，一般不会单独用来存数据。实际中更多是作为其他数据结构的子结构，如哈希桶、图的邻接表等等。
- 无头双向链表：在java的集合框架库中linkedlist底层实现就是无头双向循环链表。
2.2 链表的实现
2.2.1mysinglelinkedlist类
public class mysinglelinkedlist {
//设置内部类定义链表的结构
static class listnode {
public int val;
public listnode next;
public listnode(int val) {
this.val = val;
}
}
public listnode head;//代表链表的头结点
//创建链表
public void creatlist() {
listnode listnode1 = new listnode(12);
listnode listnode2 = new listnode(23);
listnode listnode3 = new listnode(34);
listnode listnode4 = new listnode(45);
listnode listnode5 = new listnode(56);
listnode1.next = listnode2;
listnode2.next = listnode3;
listnode3.next = listnode4;
listnode4.next = listnode5;
this.head = listnode1;
}
//打印链表
public void display() {
listnode cur = head;
while (cur != null) {
system.out.print(cur.val + " ");
cur = cur.next;
}
system.out.println();
}
//获取链表的长度
public int size() {
int count = 0;
listnode cur = head;
while (cur != null) {
count++;
cur = cur.next;
}
return count;
}
//头插法
public void addfirst(int val) {
listnode node = new listnode(val);
node.next = head;
head = node;
}
//尾插法
public void addlast(int val) {
listnode node = new listnode(val);
listnode cur = head;
if (head == null) {
head = node;
return;
}
while (cur.next != null) {
cur = cur.next;
}
cur.next = node;
}
//在任意位置插入val
public void addindex(int index, int val) {
//1. 判断index的合法性
try {
checkindex(index);
} catch (indexnotlegalexception e) {
e.printstacktrace();
}
//2. index==0 || index ==size()
if (index == 0) {
addfirst(val);
return;
}
if (index == size()) {
addlast(val);
return;
}
//3. 找到index的前一个位置
listnode cur = findindexsubone(val);
//4. 进行连接
listnode node = new listnode(val);
node.next = cur.next;
cur.next = node;
}
private listnode findindexsubone(int index) {
int count = 0;
listnode cur = head;
while (count != index - 1) {
cur = cur.next;
count++;
}
return cur;
}
private void checkindex(int index) throws indexnotlegalexception {
if (index < 0 || index > size()) {
throw new indexnotlegalexception("index不合法");
}
}
//查找是否包含关键字val是否在单链表中
public boolean contains(int val) {
listnode cur = head;
while (cur != null) {
if (cur.val == val) {
return true;
}
cur = cur.next;
}
return false;
}
//删除第一次出现关键字为val的节点
public void remove(int val) {
if (head == null) {
return;
}
if (head.val == val) {
head = head.next;
return;
}
//1.找到当前需要删除值的节点的前一个
listnode cur = head;
while (cur.next != null) {
if (cur.next.val == val) {
listnode del = cur.next;
cur.next = del.next;
return;
}
cur = cur.next;
}
}
//删除所有关键字为val的节点
public void removeallkey(int val) {
//1. 判断头结点为空
if (head == null) {
return;
}
//2. 定义prev和cur
listnode prev = head;
listnode cur = head.next;
//3. 开始判断并且删除
while (cur != null) {
if (cur.val == val) {
prev.next = cur.next;
//cur=cur.next;
} else {
prev = cur;//prev = prev.next
//cur=cur.next;
}
cur = cur.next;
}
//4. 处理头节点
if (head.val == val) {
head = head.next;
}
}
//清空链表
public void clear() {
//head=null;
listnode cur = head;
while (cur != null) {
listnode curn = cur.next;
//cur.val =null;
cur.next = null;
cur = curn;
}
head = null;
}
}
2.2.2自定义异常类
public class indexnotlegalexception extends runtimeexception {
public indexnotlegalexception() {
}
public indexnotlegalexception(string msg) {
super(msg);
}
}
2.2.3主程序代码
public class test {
public static void main(string[] args) {
mysinglelinkedlist mysinglelinkedlist = new mysinglelinkedlist();
mysinglelinkedlist.creatlist();
mysinglelinkedlist.display();
//头插法
system.out.println("头插法");
mysinglelinkedlist.addfirst(1);
mysinglelinkedlist.addfirst(2);
mysinglelinkedlist.addfirst(3);
mysinglelinkedlist.display();
//尾插法
system.out.println("尾插法");
mysinglelinkedlist.addlast(8);
mysinglelinkedlist.addlast(9);
mysinglelinkedlist.addlast(10);
mysinglelinkedlist.display();
//查找元素
boolean a=mysinglelinkedlist.contains(10);
system.out.println(a);
//删除数据为12的元素
mysinglelinkedlist.remove(12);
mysinglelinkedlist.display();
//删除所有数据为3的元素
mysinglelinkedlist.removeallkey(3);
mysinglelinkedlist.display();
//求size的长度
int size=mysinglelinkedlist.size();
system.out.println(size);
//清空链表
mysinglelinkedlist.clear();
mysinglelinkedlist.display();
}
public static void main1(string[] args) {
mysinglelinkedlist mysinglelinkedlist = new mysinglelinkedlist();
//mysinglelinkedlist.creatlist();
mysinglelinkedlist.addfirst(1);
mysinglelinkedlist.addfirst(2);
mysinglelinkedlist.addlast(5);
mysinglelinkedlist.addindex(0, 2);
//mysinglelinkedlist.remove(2);
mysinglelinkedlist.removeallkey(2);
mysinglelinkedlist.display();
system.out.println(mysinglelinkedlist.size());
system.out.println(mysinglelinkedlist.contains(5));
}
}
运行结果如下：
3.linkedlist的使用
3.1概念
linkedlist的底层是双向链表结构，由于链表没有将元素存储在连续的空间中，元素存储在单独的节点中，然后通过引用将节点连接起来了，因此在在任意位置插入或者删除元素时，不需要搬移元素，效率比较高。
在集合框架中，linkedlist也实现了list接口，具体如下：
tips:
3.2 linkedlist的构造
| 方法 | 解释 |
| linkedlist() | 无参构造 |
| public linkedlist(collection<? extends e> c) | 使用其他集合容器中元素构造list |
举个例子：
import java.util.linkedlist;
import java.util.list;
public class test {
public static void main(string[] args) {
list<integer> list1 = new linkedlist<>();
list1.add(10);
list1.add(20);
list1.add(30);
list<string> list2 = new java.util.arraylist<>();
list2.add("java");
list2.add("c++");
list2.add("python");
//使用arraylist构造linklisted
list<string> list3 = new linkedlist<>(list2);
system.out.println(list1);
system.out.println(list2);
system.out.println(list3);
}
}
运行结果如下：
3.3linkedlist的其他常用方法介绍
| 方法 | 解释 |
| boolean add(e e) | 尾插 e |
| void add(int index, e element) | 将 e 插入到 index 位置 |
| boolean addall(collection<? extends e> c) | 尾插 c 中的元素 |
| e remove(int index) | 删除 index 位置元素 |
| boolean remove(object o) | 删除遇到的第一个 o |
| e get(int index) | 获取下标 index 位置元素 |
| e set(int index, e element) | 将下标 index 位置元素设置为 element |
| void clear() | 清空 |
| boolean contains(object o) | 判断 o 是否在线性表中 |
| int indexof(object o) | 返回第一个 o 所在下标 |
| int lastindexof(object o) | 返回最后一个 o 的下标 |
| list sublist(int fromindex, int toindex) | 截取部分 list |
举个例子：
import java.util.linkedlist;
import java.util.list;
public class test {
public static void main(string[] args) {
linkedlist<integer> list = new linkedlist<>();
//添加元素，表示尾插
list.add(1);
list.add(2);
list.add(3);
list.add(4);
system.out.println(list);
//返回链表长度
system.out.println(list.size());
system.out.println();
//从起始位置插入0
list.add(0, 0);
system.out.println(list);
system.out.println();
//删除指定位置的元素
list.remove(1);
system.out.println(list);
//删除第一个元素
list.removefirst();
//删除最后一个元素
list.removelast();
system.out.println(list);
system.out.println();
//检查元素是否存在，若存在返回true，否则返回false
if (!list.contains(3)) {
system.out.println("元素不存在");
}
system.out.println();
//从前往后找到第一个指定元素值的位置
system.out.println(list.indexof(1));
//从后往前找到第一个指定元素值的位置
system.out.println(list.lastindexof(2));
system.out.println();
//获取指定位置元素
int elem = list.get(0);
system.out.println(elem);
system.out.println();
//将指定位置元素改成指定元素
system.out.println(list);
list.set(0, 100);
system.out.println(list);
system.out.println();
//sublist(from,to): 用list中[from,to)之间的元素构造一个新的linkedlist返回
list<integer> newlist = list.sublist(0, 2);
system.out.println(list);
system.out.println(newlist);
system.out.println();
//将list中的元素清空
list.clear();
system.out.println(list);
system.out.println(list.size());
}
}
运行结果如下：
3.4linkedlist的遍历
import java.util.linkedlist;
import java.util.list;
import java.util.listiterator;
public class test {
public static void main(string[] args) {
linkedlist<integer> list = new linkedlist<>();
list.add(10); // add(elem): 表示尾插
list.add(20);
list.add(30);
list.add(40);
system.out.println(list);
// foreach遍历
for (int e : list) {
system.out.print(e + " ");
}
system.out.println();
// 使用迭代器遍历---正向遍历
listiterator<integer> it = list.listiterator();
while (it.hasnext()) {
system.out.print(it.next() + " ");
}
system.out.println();
//使用反向迭代器---反向遍历
listiterator<integer> it1 = list.listiterator(list.size());
while (it1.hasprevious()) {
system.out.print(it1.previous() + " ");
}
system.out.println();
}
}运行结果如下：
4.arraylist和linkedlist的区别
| 不同点 | arraylist | linkedlist |
| 存储空间上 | 物理上一定连续 | 逻辑上连续，但物理上不一定连续 |
| 随机访问 | 支持：o(1) | 不支持：o(n) |
| 头插 | 需要搬移元素，效率低o(n) | 只需修改引用的指向，时间复杂度为o(1) |
| 插入 | 空间不够时需要扩容 | 没有容量的概念 |
| 应用场景 | 元素高效存储+频繁访问 | 任意位置插入和删除频繁 |
5.总结
以上就是本次分享链表的内容和操作链表的方法，我们要根据不同的应用场景要求，选择合适的arraylist或linkedlist，将会大大地提高学习工作效率。
发表评论