【php实现数据结构】单向链表

13次阅读

共计 2456 个字符,预计需要花费 7 分钟才能阅读完成。

什么是单向链表
链表是以链式存储数据的结构,其不需要连续的存储空间,链表中的数据以节点来表示,每个节点由元素和指针组成。
单向链表(也叫单链表)是链表中最简单的一种形式,每个节点只包含一个元素和一个指针。它有一个表头,并且除了最后一个节点外,所有节点都有其后继节点。它的存储结构如下图所示
代码实现
定义节点
class Node
{
public $data;

/**
* @var null | Node
*/
public $next;

public function __construct($data)
{
$this->data = $data;
$this->next = null;
}

}
单链表实现
/**
* Class SingleLinkList
* 单链接的实现示例,实现简单的填加,插入,删除, 查询,长度,遍历这几个简单操作
*/
class SingleLinkList
{
/**
* 链表头结点,头节点必须存在,
* @var Node
*/
public $header;

private $size = 0;

/**
* 构造函数,默认填加一个哨兵节点,该节点元素为空
* SingleLinkList constructor.
*/
public function __construct()
{
$this->header = new Node(null);
}

/**
* 添加节点
* @param Node $node
* @return int
*/
public function addNode(Node $node)
{
$current = $this->header;
while ($current->next != null) {
$current = $current->next;
}
$current->next = $node;

return ++$this->size;
}

/**
* 在指定位置查入节点
* @param int $index 节点位置,从 1 开始计数
* @param Node $node
* @return int
* @throws Exception
*/
public function insertNodeByIndex($index, Node $node)
{
if ($index < 1 || $index > ($this->size + 1)) {
throw new Exception(sprintf(‘ 你要插入的位置,超过了链表的长度 %d’, $this->size));
}

$current = $this->header;
$tempIndex = 1;
do {
if ($index == $tempIndex++) {
$node->next = $current->next;
$current->next = $node;
break;
}
} while ($current->next != null && ($current = $current->next));

return ++$this->size;
}

/**
* 删除节点
* @param int $index 节点位置,从 1 开始计数
* @return int
* @throws Exception
*/
public function deleteNodeByIndex($index)
{
if ($index < 1 || $index > ($this->size + 1)) {
throw new Exception(‘ 你删除的节点不存在 ’);
}

$current = $this->header;
$tempIndex = 1;
do {
if ($index == $tempIndex++) {
$current->next = $current->next->next;
break;
}
} while ($current->next != null && ($current = $current->next));

return –$this->size;
}

/**
* 查询节点
* @param int $index 节点位置,从 1 开始计数
* @return Node|null
* @throws Exception
*/
public function searchNodeByIndex($index) {
if ($index < 1 || $index > ($this->size + 1)) {
throw new Exception(‘ 你查询的节点不存在 ’);
}

$current = $this->header;
$tempIndex = 1;
do {
if ($index == $tempIndex++) {
return $current->next;
}
} while ($current->next != null && ($current = $current->next));
}

/**
* 获取节点长度
* @return int
*/
public function getLength()
{
return $this->size;
}

/**
* 遍历列表
*/
public function showNode()
{
$current = $this->header;
$index = 1;
while ($current->next != null) {
$current = $current->next;
echo ‘index — ‘ . $index++ . ‘ — ‘;
echo var_export($current->data);
echo PHP_EOL;
}
}
}
示例
$link = new SingleLinkList();
$link->addNode(new Node(1));
$link->addNode(new Node(2));
$link->insertNodeByIndex(3, new Node(3));
$link->addNode(new Node(4));
$link->addNode(new Node(5));
echo $link->getLength(), PHP_EOL;
$link->showNode();
echo ‘———–‘, PHP_EOL;
var_dump($link->searchNodeByIndex(3));
echo ‘———–‘, PHP_EOL;
$link->deleteNodeByIndex(3);
$link->showNode();

正文完
 0