您现在的位置是：首页 >技术教程 >【数据结构】LinkedList与链表网站首页技术教程
【数据结构】LinkedList与链表
简介【数据结构】LinkedList与链表
目录
1.链表
1.1链表的定义和分类
定义：链表在物理存储上非连续，逻辑上连续。数据元素的逻辑顺序是通过链表中的引用链接次序实现的。
分类：8种：
单向 带头 循环 双向 带头 循环
单向 带头 非循环 双向 带头 非循环
单向 不带头 循环 双向 不带头 循环
单向 不带头 非循环 双向 不带头 非循环 （LinkedList的底层）
带头与不带头：带头的头一直都是head，后面插入新数据头不变
public class MySingleList {
class ListNode {//内部类
public int val;
public ListNode next;
public ListNode(int val) {
this.val = val;
}
}
private ListNode head;//head是链表的属性，不是节点的属性
}1.2常见方法的实现
public class MySingleList {
class ListNode {//内部类，只在该外部类内部使用
public int val;//存值
public ListNode next;//存地址
public ListNode(int val) {
this.val = val;
}
}
private ListNode head;//head是链表的属性，不是节点的属性
//创建链表
public void createList() { //有了下面的addFirst方法后这个方法就淘汰了
ListNode node1 = new ListNode(1);
ListNode node2 = new ListNode(2);
ListNode node3 = new ListNode(3);
ListNode node4 = new ListNode(4);
ListNode node5 = new ListNode(5);
node1.next = node2;
node2.next = node3;
node3.next = node4;
node4.next = node5;
this.head = node1;
}
//遍历打印链表
public void show() {
ListNode cur = head;//这里只是定义了一个变量，不是new了一个新的对象，这样可以不改变head的指向
while (cur != null) {
System.out.print(cur.val+" ");
cur = cur.next;
}
System.out.println();
}
//得到单链表的长度---链表中节点的个数
public int size(){
ListNode cur = head;
int count = 0;
while (cur != null) {
count++;
cur = cur.next;
}
return count;
}
//查找链表中是否包含关键字key
public boolean contains(int key){
ListNode cur = head;
while (cur != null) {
if (cur.val == key) { //如果val值为引用类型，要用equals来比较
return true;
}
cur = cur.next;
}
return false;
}
// 头插法
public void addFirst(int data){
ListNode node = new ListNode(data);
node.next = head;
head = node;
}
//尾插法
public void addLast(int data){
ListNode node = new ListNode(data);
if (head == null) { //链表中一个节点都没有
head = node;//node直接为头
return;
}
ListNode cur = head;
while (cur.next != null) {
cur = cur.next;
}
cur.next = node;
}
//找到index-1位置的节点
private ListNode findIndex(int index) {
ListNode cur = head;
while (index-1 > 0) {
cur = cur.next;
index--;
}
return cur;
}
//找到元素key所在的节点
private ListNode findcur(int key) {
ListNode cru = head;
while (cru.next != null) {
if (cru.next.val == key) {
return cru;
}
else {
cru = cru.next;
}
}
return null;
}
//任意位置插入,第一个数据节点为0号下标
public void addIndex(int index,int data){
if (index < 0 || index > size()) {
throw new IndexOutOfBoundsException("index的位置不合法");
}
if (index == 0) { //头插
addFirst(data);
return;
}
if (index == size()) { //尾插
addLast(data);
return;
}else {
ListNode node = new ListNode(data);
ListNode cur = findIndex(index);
node.next = cur.next;
cur.next = node;
}
}
//删除第一次出现关键字为key的节点
public void remove(int key){
if (head == null) {
return;
}
if (head.val == key) {
head = head.next;
return;
}
ListNode cur = findcur(key);
if (cur == null) {
System.out.println("没有你要删除的数据");
return;
}
ListNode del = cur.next;
cur.next = del.next;
}
//删除所有值为key的节点
public void removeAllKey(int key){ //双指针
if (head == null) {
return;
}
while (head.val == key) { //或使用if循环放在最后
head = head.next;
}
ListNode cur = head;//代表当前要删除的节点
ListNode prev = head;//代表当前节点的前驱节点
while (cur != null) {
if (cur.val == key) {
prev.next = cur.next;
cur = cur.next;
}else {
prev = cur;
cur = cur.next;
}
}
}
//回收所有数据
public void clear() {
//this.head = null;//只需将头结点置为null即可
while (head != null) { //或者将每个节点置为null
ListNode headNext = head.next;
head.next = null;
head = headNext;
}
}
public static void main(String[] args) {
MySingleList mySingleList = new MySingleList();
mySingleList.createList();
mySingleList.show();//1 2 3 4 5
System.out.println(mySingleList.size());//5
System.out.println(mySingleList.contains(4));//true
System.out.println(mySingleList.contains(7));//false
mySingleList.addFirst(8);
mySingleList.addFirst(9);
mySingleList.show();//9 8 1 2 3 4 5
mySingleList.addLast(10);
mySingleList.addLast(11);
mySingleList.show();//9 8 1 2 3 4 5 10 11
mySingleList.addIndex(3,12);
mySingleList.addIndex(6,13);
mySingleList.show();//9 8 1 12 2 3 13 4 5 10 11
mySingleList.remove(13);
mySingleList.remove(18);//没有你要删除的数据
mySingleList.show();//9 8 1 12 2 3 4 5 10 11
mySingleList.addFirst(10);
mySingleList.removeAllKey(10);
mySingleList.show();//9 8 1 12 2 3 4 5 11
mySingleList.clear();
mySingleList.show();//啥都没了
}
}1.3链表面试题
这几天就发！！马上！！
2.LinkedList
2.1双向链表
2.2双向链表的模拟实现
public class MyLinkedList {
static class ListNode {
public int val;
public ListNode prev;//默认为null
public ListNode next;//默认为null
public ListNode(int val) {
this.val = val;
}
}
public ListNode head;//头
public ListNode last;//尾
//头插法
public void addFirst(int data) {
ListNode node = new ListNode(data);
if (head == null) {
head = node;
last = node;
return;//不能忘!!
}
node.next = head;
head.prev = node;
head = node;
}
//尾插法
public void addLast(int data) {
ListNode node = new ListNode(data);
if (head == null) {
head = node;
last = node;
return;
}
last.next = node;
node.prev = last;
last = node;
}
//任意位置插入,第一个数据节点为0号下标
public void addIndex(int index,int data) {
if (index < 0 || index > size()) {
throw new IndexOutOfBoundsException("index不合法");
}
if (index == 0) {
addFirst(data);
return;
}
if (index == size()) {
addLast(data);
return;
}
//找到index所在的节点
ListNode cur = head;
while (index != 0) {
cur = cur.next;
index--;
}
//开始插入
ListNode node = new ListNode(data);
node.next = cur;
cur.prev.next = node;
node.prev = cur.prev;
cur.prev = node;
}
//查找是否包含关键字key
public boolean contains(int key) {
ListNode cur = head;
while (cur != null) {
if (cur.val == key) {
return true;
}
cur = cur.next;
}
return false;
}
//删除第一次出现关键字为key的节点
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;
}
}
if (cur == last) { //删除尾节点
cur.prev.next = null;
last = last.prev;
}else { //其他情况
cur.prev.next = cur.next;
cur.next.prev = cur.prev;
}
return;
}
cur = cur.next;
}
}
//删除所有值为key的节点
public void removeAllKey(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;
}
}
if (cur == last) {
cur.prev.next = null;
last = last.prev;
}else {
cur.prev.next = cur.next;
cur.next.prev = cur.prev;
}
}
cur = cur.next;//同上，只是没有return而是一直向后走
}
}
//得到双链表的长度
public int size() {
int len = 0;
ListNode cur = head;
while (cur != null) {
cur = cur.next;
len++;
}
return len;
}
//打印双链表
public void display() {
ListNode cur = head;
while (cur != null) {
System.out.print(cur.val+" ");
cur = cur.next;
}
System.out.println();
}
//清空双链表
public void clear() {
ListNode cur = head;
while (cur != null) {
ListNode curNext = cur.next;
cur.prev = null;
cur.next = null;
//cur.val = null;//如果val是引用类型
cur = curNext;
}
head = null;
last = null;
}
}链表比顺序表难不少啊，冲冲冲！！
风语者！平时喜欢研究各种技术，目前在从事后端开发工作，热爱生活、热爱工作。
站长推荐
- stm32使用HAL库配置串口中断收发数据（保姆级教程）
stm32使用HAL库配置串口中断收发数据（保姆级教程） - SpringSecurity实现前后端分离认证授权
SpringSecurity实现前后端分离认证授权 - U8W/U8W-Mini使用与常见问题解决
U8W/U8W-Mini使用与常见问题解决 - 【社区图书馆】伴我前行的一本书《The C Programming Language》
【社区图书馆】伴我前行的一本书《The C Programming Language》 - 【云原生进阶之容器】第六章容器网络6.6.1--Cilium网络方案概述
【云原生进阶之容器】第六章容器网络6.6.1--Cilium网络方案概述