系列文章目录
前言
刚做完某厂的笔试，要求实现一个LRU算法，没有复习到LRU的我直接就凉了一半了
闲着没事把数据结构都过一遍吧，加深一下印象
作为《从零开始手撕一个数据结构》的第一篇，先从最简单的链表开始吧~
源码
点击这里获取源码，别忘了点个Star哦~
文章目录
一、要实现一个什么样的结构？
LinkedList list=new LinkedList();
list.add(3);
list.add(6);
list.add(9);
System.out.println(list.get(2)); //输出 9
System.out.println(list.toString()); //输出[3,6,9]
总所周知，LinkedList是Java中链表的一个实现类，那我们也来尝试着实现一个类似的链表容器出来
本文只把只能存放int的容器实现，不考虑泛型：
容器的实例方法
（1）void add()：对链表进行尾插
（2）int get(int index)：依据传入的索引，找到对应元素
（3）int remove(int index)：依据传入的索引，删除对应元素，并返回被删除的元素值
（4）int set(int index, int val)：依据传入的索引和值，将对应元素的值改为传入值，并返回修改前的值
（5）int size()：返回容器中的元素个数
我们的目标是把基本的增删改查做出来
二、实现步骤
1. 核心定义
首先我们要对我们要创建的容器的核心进行定义
1）创建链表容器类LinkedList
链表的英文就是linked list，就直接用它命名好了
//手写一个双向链表容器
public class LinkedList {
//定义头尾节点指针，在链表中有元素使分别指向链表的头和尾
ListNode head=null,tail=null;
//记录链表中的元素个数
int size=0;
}
在这里我们定义了两个指针和一个记录链表长度的变量，都是为了方便我们接下来对链表的操作
2）定义链表核心内部类ListNode
//内部类，双向链表的核心
private class ListNode{
//节点中存放的元素
int val;
//前、后指针
ListNode pre,next;
//构造方法
ListNode(int val){
this.val=val;
}
}
经常在leetcode上刷题的朋友应该对这个结构熟悉得不能再熟悉了，它就是一个双向链表的结构，pre指针指向自己的前一个节点，next指针指向自己的后一个节点
2. 方法实现
在我们对链表容器的核心定义完成之后，我们就可以开始实现这个容器对外提供的操作链表的方法了
1）添加元素的add方法
//添加元素方法
public void add(int val){
//往链表中添加元素时，链表长度自增
++size;
//当链表为空时
if(head==null){
//new一个链表头
head=new ListNode(val);
//由于链表里只有一个元素，所以链头和链尾是一样的
tail=head;
}else{
//链表不为空时，在链表尾插一个新节点
tail.next=new ListNode(val);
//新节点的pre指向链尾
tail.next.pre=tail;
//将链尾指针指向新节点
tail=tail.next;
}
}
注：这里只实现了尾插，想要实现头插的话用类里面的head指针可以很方便地实现，想要实现依据索引插入的话也可以根据下面在实现remove方法中实现的getNode方法方便地实现
2）查询元素的get方法
在链表中，如果用索引查询一个元素，开销是有点大的，因为程序需要把整个链表遍历一遍，直到遍历到一个符合索引值的节点才会停下来，其时间复杂度为O(n)，相比于数组索引查询的O(1)，简直太慢了
//通过索引获取元素方法
public int get(int index){
//当传入索引大于链表长度所支持的最大索引，返回-1
if(index>size-1)
return -1;
//在链表中要通过索引获取元素，要对整个链表进行遍历，时间复杂度为O(n)
//定义一个指针指向头节点，从头开始往后遍历
ListNode cur=head;
//当索引值大于0时，索引值自减，cur指针往后走一步
while(index-->0)
cur=cur.next;
//直到索引值被减为0，当前的cur指针指向的节点就是我们想要的节点
//返回节点数据
return cur.val;
}
从头开始找也太慢了呀，这我万一每次要取的元素都离尾节点近，岂不是几乎要遍历整条链表，得改进下：
//通过索引获取元素方法
public int get(int index){
//当传入索引大于链表长度所支持的最大索引，返回-1
if(index>size-1)
return -1;
//优化:当所求索引大于链表长度的一半，从尾节点开始遍历，否则从头节点开始遍历
int midIndex=size/2;
ListNode cur=null;
if(index>=midIndex){
cur=tail;
//索引也要反过来
index=size-index-1;
//反过来遍历
while(index-->0)
cur=cur.pre;
}else{
cur=head;
while(index-->0)
cur=cur.next;
}
return cur.val;
}
这样的get方法可以稍微的快一点了
3）删除元素的remove方法
写到这里一想，remove方法也需要像get方法一样一个个找呀，和我之前写的get方法也差不多，不会要再写一遍吧
再写一遍差不多的代码也太拉跨了，这里我们得重构一下
新定义一个通过索引找节点的方法getNode(int index)：
public ListNode getNode(int index) {
//当传入索引大于链表长度所支持的最大索引，返回null
if(index>size-1)
return null;
//优化:当所求索引大于链表长度的一半，从尾节点开始遍历，否则从头节点开始遍历
int midIndex=size/2;
ListNode cur=null;
if(index>=midIndex){
cur=tail;
//索引也要反过来
index=size-index-1;
//反过来遍历
while(index-->0)
cur=cur.pre;
}else{
cur=head;
while(index-->0)
cur=cur.next;
}
return cur;
}
再对get(int index)方法进行修改：
//通过索引获取元素方法
public int get(int index){
ListNode res=getNode(index);
//当getNode方法传出null时,返回-1
if(res==null) return -1;
else return res.val;
}
这样，我们写remove(int index)方法的时候就不必在写一遍遍历了：
//通过索引删除元素方法
public int remove(int index){
ListNode res=getNode(index);
//当getNode方法传出null时,返回-1
if(res==null) return -1;
//删除节点后size自减
//当size大于1时,正常自减
if(size--<=1){//当size小于等于1,删除链表中最后一个元素,头尾指针置空
head=null;
tail=null;
return res.val;
}
//若要删除的节点是尾节点，删除并返回尾节点
if(res==tail){
tail=tail.pre;
tail.next=null;
return res.val;
}
//若要删除的节点是头节点，删除并返回头节点
if(res==head){
head=head.next;
head.pre=null;
return res.val;
}
//若都不是,获取被删除节点的前后节点
ListNode pre=res.pre;
ListNode next=res.next;
//删除一个节点就是要让被删除节点的前后节点都跳过他
pre.next=next;
next.pre=pre;
//返回被删除节点的值
return res.val;
}
需要注意的是，我们在删除一个元素的时候，需要把被删除的元素的位置，当前链表的长度都考虑周全，不然的话极可能出现错误
4）修改元素的set方法
有些时候我们需要对某索引的元素值进行修改，这是我们就需要set(int index,int val)方法：
//通过索引修改元素方法
public int set(int index,int val){
//老样子,通过遍历拿到所需的节点
ListNode node=getNode(index);
int oldVal=node.val;
//直接修改对应节点的val字段即可
node.val=val;
//返回该节点被修改前的值
return oldVal;
}
5）返回当前链表长度的size方法
既然是一个容器，怎么能没有size方法呢：
//返回链表长度
public int size(){
return size;
}
我们之前写的方法都维护着容器中的size字段，直接返回size即可
6）toString方法
@Override
public String toString(){
if(size==0) return null;
StringBuilder sb = new StringBuilder();
ListNode cur = head;
while(cur != null){
sb.append(cur.val).append(",");
cur = cur.next;
}
return sb.toString();
}
遍历，组成字符串，不多说了吧
3. LRU所需要的方法
LRU的实现看这里
在上文中，LRU需要的方法有：
- 尾删
- 头插
- 查询链表中有无包含此元素
- 将一个节点移动到链表头
等等。。
1）尾删 & 头插
// 尾删方法
public int removeLast(){
// 存储链尾的值
int res = tail.val;
//尾删
tail=tail.pre;
tail.next.pre=null;
tail.next=null;
--size;
return res;
}
// 头插方法
private void addFirst(ListNode node){
node.next = head;
head.pre = node;
node.pre = null;
head = node;
++size;
}
尾删和头插方法很简单，维护好之前维护的size即可，不然很可能出现错误
2）查询链表中有无包含此元素
对于这个问题，我们只能遍历整个链表
在java.util.LinkedList中的contains方法就是用于处理此问题的，实际上它依赖于java.util.LinkedList的indexOf方法，indexOf方法的实现也是遍历整条链表，所以时间复杂度是O(N)
实现一个方法，通过值寻找节点
LinkedList的indexOf是通过值寻找索引，我们则写一个方法让它返回节点而非索引，方便我们进行内部操作
// 通过值寻找节点, 时间复杂度 O(n)
private ListNode getNodeByVal(int val){
ListNode cur = head;
while (cur != null){
if(cur.val == val) return cur;
cur = cur.next;
}
return null;
}
有了以上的方法，我们就可以简单的实现contains方法
// 查询链表是否包含所传入值
public boolean contains(int val){
return getNodeByVal(val)!=null;
}
3）将一个节点移动到链表头
在实现这个方法之前，我们先实现一个方法用于删除指定节点
// 删除指定节点方法
private void removeNode(ListNode node){
ListNode nodePre = node.pre;
ListNode nodeNext = node.next;
nodePre.next = nodeNext;
nodeNext.pre = nodePre;
--size;
}
(有增删操作时记得维护好size。。)
// 将节点移到链头
public boolean moveToHead(int val){
// 用 node记录被移动节点
ListNode node;
// 当链表中不存在这个值，返回 false
// 这里我们为了快速获取到 node值，就不用 contains了
if ((node = getNodeByVal(val)) == null)
return false;
// 分情况讨论：node为头节点？尾节点？还是其它节点
if(node == head) // 若 node本就是头节点，无需移动
return true;
// 当 node不是尾节点
if (node != tail){
removeNode(node);
}else { // node是尾节点时，先尾删
removeLast();
}
//将node头插
addFirst(node);
return true;
}
总结
自此，一个链表容器基本的增删改查就写好了，测试如下：
LinkedList l=new LinkedList();
// add 测试 正常
l.add(3);
l.add(6);
l.add(1);
// moveToHead 测试 正常
System.out.println(l.toString()); // 3,6,1,
System.out.println(l.moveToHead(1)); // true
System.out.println(l.toString()); // 1,3,6, (移动成功)
System.out.println(l.moveToHead(3)); // true
System.out.println(l.toString());
// contains 测试 正常
System.out.println(l.contains(3)); // true (链表中有值3
System.out.println(l.contains(5)); // false (链表中没有值5
// removeLast 测试 正常
l.removeLast();
System.out.println(l.toString()+" | removeLast"); // 3,1, | removeLast
// remove(int index) 测试 正常
System.out.println(l.size()); // 2
System.out.println(l.remove(2)); // -1
System.out.println(l.toString()); // 3,1,
System.out.println(l.remove(0)); //3
System.out.println(l.toString()); // 1,
System.out.println(l.remove(0)); //1
System.out.println(l.toString()); // null
// set(int index, int val) 测试 正常
l.add(9);
l.add(7);
System.out.println(l.toString()); // 9,7,
System.out.println(l.set(0,3)); //9
System.out.println(l.toString()); // 3,7,
欢迎有更好想法的朋友在评论区提意见，有问题也可以在评论区留言~