Skip to content

Latest commit

 

History

History
177 lines (143 loc) · 4.26 KB

单向链表.md

File metadata and controls

177 lines (143 loc) · 4.26 KB

单向链表

单向链表

目录

知识准备

链式存储的原理

1. 链式存储中每个结点都包含两个部分: 存储元素本身的数据域和存储结点地址的指针域.

2. 一般在链表中会有一个头结点保存链表的信息, 然后有一个指针指向下一个结点, 下一个结点又指向它后面一个结点,
   这样直到最后一个结点, 它没有后继结点, 就指向NULL.
   
3. 在链表中某一个位置插入元素时, 将两个结点之间的指针断开, 上个结点的指针指向新分配的单元, 新分配的结点中
   指针指向下一个结点, 这样不需要移动原来元素的位置, 效率比较高.
   
4. 当删除链表中某个元素时, 就断开它与前后两个结点的指针, 然后将它的前后两个结点连接起来, 不需要移动原来
   元素的位置.
   
5. 与顺序存储结构相比, 链表在插入、删除方面效率较高, 但是在查找元素时, 链表由于存储空间不连续, 如果要查找
   某一元素, 必须得经过它前面的结点, 因此查找的效率比顺序存储结构低.

代码实现

class Node
{
    public $data;
    public $next = NULL;

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

class SingleLinkedList
{
    // 头结点
    private $head = NULL;
    // 长度
    private $length = 0;

    // 插入元素
    public function insert($data)
    {
        $node = new Node($data);

        if ($this->head == NULL) {
            $this->head = $node;
        } else {
            $currNode = $this->head;
            while ($currNode->next != NULL) {
                $currNode = $currNode->next;
            }
            $currNode->next = $node;
        }

        $this->length++;
    }

    // 删除元素
    public function delete($data)
    {
        if ($this->head == NULL) {
            throw new Exception('LinkedList is NULL');
        }

        // 头结点
        if ($this->head->data == $data) {
            $this->head = $this->head->next;
            $this->length--;
            return true;
        }
        // 非头结点
        else {
            $currNode = $this->head;
            while ($currNode->next != NULL && $currNode->next->data == $data) {
                $currNode->next = $currNode->next->next;
                $this->length--;
                return true;
            }
        }

        return false;
    }

    // 遍历打印
    public function display()
    {
        echo 'LinkedList length: ' . $this->length . PHP_EOL;

        $currNode = $this->head;
        while ($currNode != NULL) {
            echo $currNode->data . PHP_EOL;
            $currNode = $currNode->next;
        }
    }

    // 查找元素
    public function find($data)
    {
        if ($this->length > 0) {
            $currNode = $this->head;

            while ($currNode != NULL) {
                if ($currNode->data == $data) {
                    echo 'found' . PHP_EOL;
                    return true;
                }

                $currNode = $currNode->next;
            }
        }

        echo 'not found';
        return false;
    }

    // 反转链表
    public function reverse()
    {
        if ($this->head != NULL && $this->head->next != NULL) {
            $reversedList = NULL;
            $currNode = $this->head;

            while ($currNode !== NULL) {
                $next = $currNode->next;
                $currNode->next = $reversedList;
                $reversedList = $currNode;
                $currNode = $next;
            }
            $this->head = $reversedList;
        }
    }
}

// Test
$list = new SingleLinkedList();
$list->insert(1);
$list->insert(2);
$list->insert(3);

// LinkedList length: 3
// 1 2 3
$list->display();

$list->reverse();
$list->display();
$list->reverse();

// found
$list->find(2);

// LinkedList length: 2
// 1 3
$list->delete(2);
$list->display();

// LinkedList length: 1
// 3
$list->delete(1);
$list->display();

// not found
$list->find(1);

// bool(false)
var_dump($list->delete(1));