PHP: как в односвязном списке удалить из середины элемент по его номеру?

Question

[Valentine5]

Ниже привожу код. У меня получается в if ($i == $levelToCut) отловить уровень списка, который нужно удалить, но не понимаю, как склеить потом оставшиеся части. Пробовал поменять список задним числом с помощью ссылки &, но и так не выходит. Подскажите, пожалуйста, как можно решить проблему?

/list.php

class Node
{
    public $data;
    public $next;

    function __construct($data, $next = null)
    {
        $this->data = $data;
        $this->next = $next;
    }
}
/index.php

require_once('list.php');
$ari = new Node('Ari');
$malcolm = new Node('Malcolm', $ari);
$pete = new Node('Pete', $malcolm);
$ricky = new Node('Ricky', $pete);
$sean = new Node('Sean', $ricky);

cut($sean, 3);


function cut($head, $levelToCut)
{

    $i = 1;
    $temp = $head;

    while (!empty($temp->next)) {

        if ($i == $levelToCut) {

            $temp = $temp->next;
        }

        if($i !== 1) {
            $temp = $temp->next;
        }
        $i++;
    }
}

Comments

[Adamos]

У вас нет ощущения, что вы решаете задачу через жопу?
Если вам нужно работать с элементами по номеру - зачем хранить их в односвязном списке?
Чтобы героичнее стоялось в гамаке?

Впрочем, что у вас за проблема с удалением одного элемента - непонятно.
Предыдущему в next записывается next из целевого элемента, и все - он готов к удалению.
Предыдущий у вас есть, раз уж вы все перебираете подряд.

[Valentine5]

Adamos, я вот так "получаю" Малкольма:

if ($i == $levelToCut) {

$temp = $temp->next;
print_r($temp->next);
}

но к этому моменту у меня уже пропал верх списка "шон", "рики" съедены, потому что $temp каждый раз продвигается вперед выкидывая то, что сзади. Я бы мог использовать $head, но как сделать так, чтобы он отрезал из головы списка столько, сколько нужно, чтобы его склеить с огрызком $temp после удаления Пита.

Со списками работаю, потому что задание учебное такое...

Answer 1

[Дмитрий]

<?php
class Node
{
    public $data;
    public $next;

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

class LinkedList{

    public $head = null;

    public function push(Node $node){
        if($this->head == null){
            $this->head = $node;
            return $this;
        }

        $current = $this->head;
        while($current->next != null) {
            $current = $current->next;
        }

        $current->next = $node;
        return $this;
    }

    public function cut(int $index){
        if($index == 0){
            $this->head = $this->head->next;
            return $this;
        }

        $i = 0;
        $previous = null;
        $current = $this->head;
        do {
            if($i == $index){
                $previous->next = $current->next;
                return $this;
            }
            $previous = $current;
            $i++;
        }while(($current = $current->next) != null);

        throw new Exception('Надо эксепшен что бы out of bounds');
    }

    public function printList()
    {
        if(!$this->head){
            echo 'empty list'.PHP_EOL;
            return $this;
        }
        $current = $this->head;

        echo $current->data.' -> ';
        while (($current = $current->next)) {
            echo $current->data;

            if($current->next) {
                echo ' -> ';
            }
        }

        echo PHP_EOL;

        return $this;
    }

}

$linkedList = new LinkedList();

$linkedList
    ->push(new Node('Ari'))
    ->push(new Node('Malcolm'))
    ->push(new Node('Pete'))
    ->push(new Node('Ricky'))
    ->push(new Node('Sean'));
$linkedList
    ->printList()
    ->cut(2)
    ->printList()
    ->cut(1)
    ->printList()
    ->cut(10);

Comments

[Valentine5]

Дмитрий, спасибо за помощь, сейчас попробую так сделать!

[Valentine5]

Дмитрий, все работает, вот что значит специалист!

Answer 2

[Wataru]

Подсказка: вам надо найти не levelToCut-ый элемент, а элемент с номером levelToCut-1, ведь это у него надо перезаписать next на next->next

Comments

[Valentine5]

Мне кажется, я понял вашу мысль. Я пробовал так:

$searchStr[] = '->next';
print_r($temp.implode($searchStr));

но так выдается ошибка о том, что вы пытаетесь объект в строку перевести..

[Дмитрий]

Valentine5, а эта конструкция $temp.implode($searchStr) откуда? из js?

[Valentine5]

Дмитрий, нет php.. Implode склейка всех элементов массива. Точка - конкатенация, должно было получиьься $temp->next-next... Нужно количество в соответствии со значением $i

[Дмитрий]

Valentine5, нееее в php будет implode($clue, $array). да и обращение к методу или свойству не через . а через ->

[Valentine5]

Дмитрий, вы правы, попробую с разделителем.. Может в этом и было дело..

[Дмитрий]

Valentine5, вообще не в этом. в вашем коде никаких операций над списком не происходит, так что работать он не будет.

[Valentine5]

Потому, что я просто не знаю, что делать ( перемещаться по годам я могу только вот так $temp = $temp->next, но при этом у меня впадает начало списка : Шон, Рикки и другие товарищи.. Я могу пропустить в условиях Пита и отловить нод, который был до него и под после - Малкольм, но начало списка у меня уже потерялось..

[Valentine5]

Дмитрий, Потому, что я просто не знаю, что делать ( перемещаться по годам я могу только вот так $temp = $temp->next, но при этом у меня впадает начало списка : Шон, Рикки и другие товарищи.. Я могу пропустить в условиях Пита и отловить нод, который был до него и под после - Малкольм, но начало списка у меня уже потерялось..

[Дмитрий]

Valentine5, а зачем вам помнить начало списка? как бы по аргументам функции не совсем понятно что вы хотите вырезать.

[Valentine5]

Дмитрий, function cut($head, $levelToCut) $head это головной элемент списка,включающий всё ноды, а $levelToCut число - 2, 3, 4 в зависимости от того, какой именно элемент по счету от начала списка надо удалить. В данном случае значение переменной 3, удаляю Пита..

[Дмитрий]

Valentine5, ну $shean который вы передаете в cut - не головной элемент списка.

[Valentine5]

Дмитрий, а начало списка тре.уется, так как нужно в итоге список получить в том же виде, в каком он был, но без Пита.. Я понимаю, что нужно в нужный $temp->next положить не вместо объекта пит, объект малкольм, а потом очистить ненужный нод, но у меня это не выходит

[Valentine5]

Valentine5, Дмитрий, да, неточно выразился головной ari , но суть таже.. Ari указывает на null, поэтому перебрать ноды могу только от Шона, которого назвал головным, хотя он последний скорее