创建链表

创建一个单项链表。

<?php
/**
 * Created by PhpStorm.
 * User: zooeymoon
 * Date: 2018/5/15
 * Time: 23:46
 */

class Node{

    public $element;
    public $next;

    public function __construct($element,$next = null)
    {
        $this->element = $element;
        $this->next = $next;

    }

}


class LinkedList{

    public $head;

    public function __construct($head = "head")
    {
        $this->head = new Node($head);
    }

    /**
     * 查找元素是否在链表中
     * @param $item
     * @return Node|null
     */
    public function find($item)
    {
        $currNode = $this->head;

        while ($currNode->element != $item){
            $currNode = $currNode->next;
        }

        return $currNode;
    }

    /**
     * 向链表中插入一个元素
     * @param $newElement
     * @param $item
     */
    public function insert($newElement , $item)
    {
        $newNode = new Node($newElement);
        $current = $this->find($item);

        $newNode->next = $current->next;
        $current->next = $newNode;

    }

    public function display()
    {
        $currNode = $this->head;

        while ($currNode != null){
            echo $currNode->next->element;
            echo "<br/>";
            $currNode = $currNode->next;
        }
    }

    /**
     * 从链表中删除一个元素
     * 首先找到待删除元素的前一个元素
     * @param $item
     */
    public function remove($item)
    {
        $prevNode = $this->findPrevious($item);

        if($prevNode->next != null){

            $prevNode->next = $prevNode->next->next;

        }

    }

    /**
     * 找到置顶元素的链表前一个元素
     * @param $item
     * @return Node|null
     */
    public function findPrevious($item)
    {
        $currNode = $this->head;

        while (($currNode->next != null) && ($currNode->next->element != $item)){
            $currNode = $currNode->next;
        }

        return $currNode;
    }


}

$llist = new LinkedList();
$llist->insert("Conway","head");
$llist->insert("Russellville","Conway");
$llist->insert("Carlisle","Russellville");
$llist->insert("Alma","Carlisle");
$llist->display();

$llist->remove("Carlisle");
$llist->display();