<?php
/**
* 链表和数组的区别就是 数据是个有序的内存空间 链表是个无序的内存空间但是可以把有序的内存空间连续起来
* 链表是一种代码的实现逻辑并不是底层的 链表每增加一个节点就会随机向内存申请一个内存地址 而数组是直接向内存申请一个有序内存空间
*
* 数组在操作 添加 修改 删除节点时候都是在整体移动 而链表不是 链表则是重新该表指针的指向 操作起来要比数组快
*
*查询的时间复杂度就没有数组那么快了 是不是要扫扫去全表 全部链表 必须要从链表的头部开始进行查找,一个一个去遍历,直到找到自己想要的元素
* 类似于 for 循环全表查询时间复杂度 O(n)
*
*
* 链表几个特性:
* 头部指向第一个节点
* head
* |
* node = {value,next} = first_node;
* |
* node = {value,next} = next_node;
* |
* node = {value,next} = next_node;
* |
* node = {value,next} = last_node; 指向最后一个 null
* |
* null
* 单链表
*
* 循环链表
*
*实在单项链表上面的升级 ,循环链表尾部不在指向null 而是指向头部指向的第一个节点 闭合形成了一个圆
*
* head
* |
* node = {value,next} = first_node;
* |
* node = {value,next} = next_node;
* |
* node = {value,next} = next_node;
* |
* node = {value,next} = last_node; 指向最后一个 null
* |
* first_node
*
* 双向链表
*
*双向链表在单项链表的基础每个节点增加了指向上一个节点
*
* * head
* |
* node = {value,next,prev} = first_node;
* |
* node = {value,next,prev} = next_node;
* |
* node = {value,next,prev} = next_node;
* |
* node = {value,next,prev} = last_node; 指向最后一个 null
* |
* first_node
*
*
* LRU的全称为Least Recently Used,它是一种内存数据淘汰算法
* 类似于清理衣柜里面的衣服
*
* 分为三类
*
* old 衣服 不穿了
* ing 已经不怎么穿的衣服
* recently 衣服 常穿的衣服
*
*
*/
/**
* 单项链表节点 没有索引位置这个说话 其实就是 每个自己的主要节点的信息 附加下一节点的地址
*
* 单向链表就是一个思想 算法 每个节点可以承载更多的信息 附加下一个节点信息
*/
class Node {
public ?string $selfInfo = null;
public ?string $nodeId = null;//删除的时候使用
public ?Node $nextNode = null;//存放下一个节点
/**
* Node constructor.
* @param string $nodeId
* @param string $selfInfo
*/
public function __construct(?string $nodeId, ?string $selfInfo)
{
$this->nodeId = $nodeId;
$this->selfInfo = $selfInfo;
}
/**
* @return Node
*/
public function getNextNode(): ?Node
{
return $this->nextNode;
}
/**
* @param Node $nextNode
*/
public function setNextNode(?Node $nextNode): void
{
$this->nextNode = $nextNode;
}
/**
* @return string
*/
public function getSelfInfo(): string
{
return $this->selfInfo;
}
/**
* @return sting|string
*/
public function getNodeId()
{
return $this->nodeId;
}
/**
* @param sting|string $nodeId
*/
public function setNodeId($nodeId): void
{
$this->nodeId = $nodeId;
}
}
/**
* 链表列表
*/
class LinkList {
/**
* @var Node
*/
protected Node $head ; //虚拟节点头
protected int $size; //链表长度
protected static Node $lastNode;
protected static Node $firstNode;
protected static int $count;
public static $ins;
static function getIns(...$arg):LinkList {
if(empty(self::$ins)){
self::$ins = new static();
}
return self::$ins;
}
/**构造函数
* LinkList constructor.
* @param string $type
*/
public function __construct(string $type)
{
$this->head = new Node("0","head");//初始化
$this->size = 0;//链表长度刚开始是0
}
//
public function add(Node $addNode):self {
//判断头部有没有节点
if(empty($this->head->getNextNode())) {
$this->head->setNextNode($addNode);
$this->size++;
self::$lastNode = $addNode;
return $this;
}
//头部有节点就开始有序往后添加
// $curNode = $this->head;
// while (!empty($curNode->getNextNode())){
// $curNode = $curNode->getNextNode();//重置当前节点往下遍历 可以理解指针后移
// }
// $curNode->setNextNode($addNode);
// return $addNode;
//这里可有优化一下 不用每次添加节点的时候都要重头遍历 时间复杂度太高了
// 可以利用累的静态变量来存储最后一个节点
// 这样在每次添加的时候就可以直接引用这里最后一个节点 就不用再从头遍历了
self::$lastNode->setNextNode($addNode); //上一个最后节点指向新加的节点
self::$lastNode=$addNode; //新加的节点就会变成最后一个节点
return $this;
}
/**
* 实现有序链表
* @param Node $addListNode
* @return $this
* @throws Exception
*/
public function addList(Node $addListNode):self {
//头部节点要是没有第一个节点就判断添加的节点是不是1
if(empty($this->head->getNextNode())){
if((int)$addListNode->getNodeId()>1) {
throw new Exception("添加节点的数量大于有序列表最大值".$this->head->getNodeId(),1000);
}
}
$curNode = $this->head;
while (!empty($curNode->getNextNode())) {
// 判断当前已有的节点ID是否大于要加入的节点ID,如果大于则break
$curNode = $curNode->getNextNode();//重置当前节点往下遍历 可以理解指针后移
if((int)$curNode->getNodeId() >= (int)$addListNode->getNodeId())
{
throw new Exception("添加节点的数量应该有序列表最大值".$curNode->getNodeId(),1000);
}
}
if((int)$addListNode->getNodeId() > (int)$curNode->getNodeId()+1 ){
throw new Exception("添加".$addListNode->getNodeId()."节点的数量应该小于等于".((int)$curNode->getNodeId()+1),1000);
}
$curNode->setNextNode($addListNode);
return $this;
}
// 获取链表长度
public function getLinkSize() {
$curNode = $this->head;
$num = 0;
while(!empty($curNode->getNextNode())) {
$num ++;
$curNode = $curNode->getNextNode();
}
return $num;
}
/**
* 添加循环链表
* @param Node $cycleNode
*/
public function addCycleLink(Node $cycleNode):self {
//空链表
if(empty($this->head->getNextNode())){
$cycleNode->setNextNode($this->head);
$this->head->setNextNode($cycleNode);
return $this;
}
//获取最后的节点最后的节点指向头部
}
public function update(int $index,Node $node){
}
public function delete(Node $delNode):self {
$curNode = $this->head;
while (!empty($curNode->getNextNode())){
$curNode = $curNode->getNextNode();//重置当前节点往下遍历 可以理解指针后移
//节点id 要是对上了就删除当前节点 为了保障链表的连续性 删除了当前节点的要把上个节点和删除后的下个节点老地址连接上
//这里要有个注意的点进行修正 如果用当前节点进行删除的话 无法记录了上一个节点 所以这里要用当前节点的下一个节点进行比对 如果下一个节点对上上了 就直接修改下一个节点的指向
if($curNode->getNextNode()->getNodeId() ==$delNode->getNodeId()){
if(empty($curNode->getNextNode()->getNextNode())){
//最后一个节点
$curNode->setNextNode(null);//连接删除节点的上一个节点和删除的下一个节点
$this->size--;
break;
}
$delNodeAfter = $curNode->getNextNode()->getNextNode();//记录要删除节点后的所有节点
$curNode->setNextNode($delNodeAfter);//连接删除节点的上一个节点和删除的下一个节点
break;
}
}
return $this;
}
public function toString():self {
$str = "head->";
$curNode = $this->head;
while (!empty($curNode->getNextNode())){
$curNode = $curNode->getNextNode();//重置当前节点往下遍历 可以理解指针后移
if(empty($curNode->getNextNode())){
$str.=$curNode->getNodeId()."->end";
break;
}
$str.=$curNode->getNodeId()."->";
}
echo $str. " size = ".$this->getLinkSize().PHP_EOL;
return $this;
}
public function search(Node $node):int
{
$index = 0;
return $index;
}
}
(new linkList)
->add(new Node("1","1"))
->add(new Node("3","3"))
->add(new Node("4","4"))
->add(new Node("2","2"))
->toString()
->delete(new Node("2","2"))
->toString();
(new linkList)
->addList(new Node("1","1"))
->addList(new Node("2","2"))
->addList(new Node("3","3"))
->toString()
->addList(new Node("5","3"))
->toString();