那么我们正式踏入了对数据结构的学习 本篇博客教大家学习单链表 以下为代码实现的思维导图
本篇代码较多,我会在代码块中,进行许多的注释讲解,想要理解清楚的小伙伴一定要点开来耐心看完哦
单链表的概念
链表是一种物理存储结构上非连续存储结构,数据元素的逻辑顺序是通过链表中的引用链接次序实现的 。
链式的结构分为一个一个节点,什么是节点呢?
节点:
- 数值域
- next域(可以理解为指针域或是引用域)
注意:👇
- 那么我们在下面的图中可以看出,链式结构在逻辑上是连续的,但是在物理上不一定连续
- 现实中的节点一般都是从堆上申请的
- 从堆上申请的空间,是按照一定的策略来分配的,两次申请的空间可能连续,也可能不连续,下图中的0×11,0×12就是连续的特殊情况
这样单向,带头,非循环的,我们称其中的节点为傀儡节点,那么什么是双向呢?
那么什么是不带头的呢?,就是没有数值域为空的节点
那么什么是循环呢?就是最后的next域不指向null,而是指向首节点,构成循环
这些条件排列组合一下会产生许许多多的链表,但我们常用的链表主要是以下两种:
- 无头单项肺循环链表:结构比较简单,一般不会单独用来存储数据。实际上更多是作为其他数据结构的子结构。
- 无头双向链表:在Java的集合框架库中LinkedList底层实现就是无头双向循环链表。
单链表的实现
/**
* @author Gremmie102
* @date 2022/4/28 9:24
* @purpose :单链表的实现
*/
public class MySingleList {
static class ListNode {
public int val;//数值域
public ListNode next;//存储下一个节点的地址
public ListNode(int val) {
this.val = val;
}
}
public ListNode head;//代表单链表的头结点的引用
/**
* 这里只是简单的进行,链表的构造。
*/
public void createList() {
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();
}
/**
* 头插法
* O(1)
*/
public void addFirst(int data){
ListNode node = new ListNode(data);
/*if(this.head == null) {
this.head = node;
}else {
node.next = this.head;
this.head = node;
}*/
node.next = this.head;
this.head = node;
}
//尾插法 O(n)
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 == null;
cur.next = node;
}
}
/**
* 任意位置插入,第一个数据节点为0号下标
* 指定位置插入
*/
public void addIndex(int index,int data) throws MySingleListIndexOutOfException{
checkIndexAdd(index);
if(index == 0) {
addFirst(data);
return;
}
if(index == size()) {
addLast(data);
return;
}
ListNode node = new ListNode(data);
ListNode cur = findIndexSubOne(index);
node.next = cur.next;
cur.next = node;
}
/**
* 找到index-1位置的节点
* @param index
* @return 该节点的地址
*/
private ListNode findIndexSubOne(int index) {
ListNode cur = this.head;
while (index-1 != 0) {
cur = cur.next;
index--;
}
return cur;
}
private void checkIndexAdd(int index) {
if(index < 0 || index > size()) {
throw new MySingleListIndexOutOfException("任意位置插入的时候,index不合法!");
}
}
//查找是否包含关键字key是否在单链表当中 314
public boolean contains(int key) {
//head == null
ListNode cur = this.head;
//cur != null 说明 没有遍历完 链表
while (cur != null) {
if(cur.val == key) {
return true;
}
cur = cur.next;
}
return false;
}
//删除第一次出现关键字为key的节点
public void remove(int key){
if(this.head == null) {
System.out.println("此时链表为空,不能进行删除!");
return;
}
if(this.head.val == key) {
//判断 第一个节点是不是等于我要删除的节点
this.head = this.head.next;
return;
}
ListNode cur = this.head;
while (cur.next != null) {
if(cur.next.val == key) {
//进行删除了
ListNode del = cur.next;
cur.next = del.next;
return;
}
cur = cur.next;
}
}
//删除所有值为key的节点
public void removeAllKey(int key){
while(true){
remove(key);
if (this.contains(key)){
continue;
}else break;
}
}
//得到单链表的长度
public int size(){
int count = 0;
ListNode cur = this.head;
while (cur != null) {
count++;
cur = cur.next;
}
return count;
}
public void clear(){
this.head = null;
}
}
LinkedList
那么上面的代码是我们自己实现的单链表。
在Java中,已经有大佬帮我们写好了单链表,叫做LinkedList
使用方式
方法
method | explain |
---|---|
void add(int index, E element) | 将 e 插入到 index 位置 |
boolean add(E e) | 尾插 e |
boolean addAll(Collection 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 lastIndexOf(Object o) | 返回最后一个 o 的下标 |
int indexOf(Object o) | 返回第一个 o 所在下标 |
List subList(int fromIndex, int toIndex) | 截取部分 list |
public 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);
// 在起始位置插入0
list.add(0, 0); // add(index, elem): 在index位置插入元素elem
System.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,否则返回false
if(!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位置的元素设置为elem
System.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());
}
链表后续还会更新题目,大家拭目以待
最近临近考试,学习任务繁重
如果文章有哪里不足的地方麻烦大佬指出
感谢阅读~