current community

your communities

more stack exchange communities

Stack Exchange
tour help
Take the 2-minute tour ×
Code Review Stack Exchange is a question and answer site for peer programmer code reviews. It's 100% free, no registration required.
up vote 2 down vote favorite

This is how my LinkedList class looks like in PHP. I am trying to figure out if I can rewrite my reverse_list_recursively() function more elegantly without having the funky $current = NULL. The reason I have it is because I need to pass $current in my recursion call. I'm not sure if there is another way to do it.

<?php

class ListNode {
    public $data;
    public $next;

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

    function getData() {
        return $this->data;
    }
}

class LinkList {

    // points to the first node
    private $head;

    // node count
    private $count;

    function __construct() {
        $this->head = NULL;
        $this->count = 0;
    }

    // checks if the list is empty or not
    function is_empty() {
        return ($this->head == NULL);
    }

    // inserts data at the beginning of the list
    public function insert_beg($data) {

        $link = new ListNode($data);
        $link->next = $this->head;
        $this->head = &$link;
        $this->count++;
    }

    public function insert_last($data) {
        $current = $this->head;

        if($current == NULL) {
           $this->insert_beg($data);

        } else {

            while($current->next != NULL) {
                $current = $current->next;
            }
            $link = new ListNode($data);
            $current->next = &$link;
            $link->next = NULL;
            $this->count++;
        }
    }

    public function delete_first_node() {
        if($this->head != NULL) {
            if($this->head->next != NULL) {
                $this->head = $this->head->next;
                $this->count--;
            }
        }
    }

    public function delete_last_node() {

        $current = $this->head;
        if($current != NULL) {

            $prev = $current;
            while($current->next != NULL) {
                $prev = $current;
                $current = $current->next;
            }
            $current = $prev;
            $current->next = NULL;
            $this->count--;
        }
    }

    public function delete_node($data) {
        $current = $prev = $this->head;
        if ($current == NULL) {
            return;
        } else {
            while($current->data != $data && $current->next != NULL) {
                $prev = $current;
                $current = $current->next;
            }
            if($current->data == $data) {
                $prev->next = $current->next;
                $this->count--;
            }
            return;
        }
    }

    public function reverse_list_iteratively() {
        $current = $this->head;

        // if the list is empty or only one element in the list return
        if($current == NULL || $current->next == NULL) {
            return;
        } else {
            $next = $prev = NULL;
            while($current != NULL) {
                $next = $current->next;
                $current->next = $prev;
                $prev = $current;
                $current = $next;

            }
            $this->head = $prev;
        }
    }

    public function reverse_list_recursively($current = NULL) {
        $current = $this->head;

        // base case when the current is empty
        if($current->next == NULL) {
            $this->head = $current;
            return $current;
        } else {
            $this->reverse_list_recursively($current->next);
            $current->next->next = $current;
            $current->next = NULL;
        }

    }

    public function print_list() {
        $current = $this->head;
        echo "\nThe list is: ";
        while($current != NULL) {
            echo "$current->data" . " ";
            $current = $current->next;
        }
    }

    public function get_size() {
        return $this->count;
    }

}
    $totalNodes = 10;

    $list = new LinkList();


    echo "Is list empty before adding nodes: ";
    var_export( $list->is_empty());
    echo "\n";

    for($i=1; $i <= $totalNodes; $i++) {
        $list->insert_last($i);
    }

    echo "Is list empty after adding nodes: "; 
    var_export( $list->is_empty());
    echo "\n";

    echo "Size of the list: " .  $list->get_size();
    echo "\n";

    echo "List is: ";
    $list->print_list();
    echo "\n";


    echo "Deleting first node: ";
    $list->delete_first_node();
    $list->print_list();
    echo "\n";

    echo "Deleting last node: ";
    $list->delete_last_node();
    $list->print_list();
    echo "\n";

    echo "Deleting node 6: ";
    $list->delete_node(6);
    $list->print_list();
    echo "\n";

    echo "Reversing the list iteratively";
    $list->reverse_list_iteratively();
    $list->print_list();
    echo "\n";

    echo "Reversing the list rec";
    $list->reverse_list_iteratively();
    $list->print_list();
    echo "\n";



?>

Results:

Is list empty before adding nodes: true
Is list empty after adding nodes: false
Size of the list: 10
List is: 
The list is: 1 2 3 4 5 6 7 8 9 10 
Deleting first node: 
The list is: 2 3 4 5 6 7 8 9 10 
Deleting last node: 
The list is: 2 3 4 5 6 7 8 9 
Deleting node 6: 
The list is: 2 3 4 5 7 8 9 
Reversing the list iteratively
The list is: 9 8 7 5 4 3 2 
Reversing the list rec
The list is: 2 3 4 5 7 8 9
share|improve this question

1 Answer 1

up vote 1 down vote

Let's start by looking at your code. First notice that you do not actually test your reverse_list_recursively method. This can be seen by looking at 

  echo "Reversing the list rec";
  $list->reverse_list_iteratively();
  $list->print_list();
  echo "\n";

You are actually just calling reverse_list_iteratively again.

In fact, your recursive implementation doesn't work at all. Let's take a look at it.

public function reverse_list_recursively($current = NULL) {
    $current = $this->head;

    // base case when the current is empty
    if($current->next == NULL) {
        $this->head = $current;
        return $current;
    } else {
        reverse_list_recursively($current->next);
        $current->next->next = $current;
        $current->next = NULL;
    }

}

Notice that you pass in the parameter $current, but then the first thing you do is assign to $current, so that the argument the function is called with has no effect. Any time this function is called, $current will wind up having the value $this->head. Then assume this LinkList is not empty, the first if will never evaluate to true, so that the function evaluation will always precede to the recursive function call. Thus we get into a infinite recursion which will lead to a stack overflow. We have come full circle.

Also, since your recursive function call is actually calling a method and not a function, the line

    reverse_list_recursively($current->next);

should really be

    $this->reverse_list_recursively($current->next);

There are a few other problems. For one thing, when the if branch is taken, you return a value. This doesn't make sense because reversing a list shouldn't return a value, and you don't return a value when the if branch isn't taken.

Another problem is that you always set $current->next = NULL, but if in your recursion, you are somewhere in the middle of the list, then you do not want $current->next==NULL, instead you want $current->next to be the node that had originally been before $current.

Now I wrote an implementation. Let's look at it.

    private function reverse_list_right_of_node($node) {
        //We have reached the end.
        //This is where our head goes.
        if($node->next==NULL){ 
            $this->head = $node;
            return;
        }
        $nextNode = $node->next;
        //recursively reverse the rest of the list after the next node
        $this->reverse_list_right_of_node($nextNode); 
        //reverse nextNode
        $nextNode->next=$node; 
    }

    public function reverse_list_recursively() {
       $head=$this->head;
       //reverse everything to the right of head
       $this->reverse_list_right_of_node($head);
       //make head point to null (if list is non-empty)
        if($head!=NULL){
            $head->next=NULL;
        }
    }

The first method is a helper method that recursively reverses a part of the list to the right of a given $node. If $node->next is is NULL, then $node ought to become the head node. Otherwise, you can recursively reverse everything to the right of $node, and then reverse the connection between $node and $nextNode.

Then I use this helper method to implement the reverse_list_recursively() method. In this method you simply reverse everything to the right of the head node and then make the head node point to NULL since it is to become the last node.

Now there is a way to do this without the helper method

    public function reverse_list_recursively($node=NULL) {
        //treat $node==NULL as a special case
        $topLevel=false;
        if(!$node){
            $node=$this->head;
            $topLevel=true;
        }
        if($node->next==NULL){ 
            $this->head = $node;
            return;
        }
        $nextNode = $node->next;
        //special case: set original head node to point to NULL
        if($topLevel){
            $node->next=NULL;
        }
        $this->reverse_list_recursively($nextNode); 
        $nextNode->next=$node; 
    }

I have given and implementation below. You give the $node a default value and test for the default value, and handle things specially in that case. I think this looks uglier and is harder to understand than the other implementation I gave.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.