in reply to Re^7: [OT:] Is this Curriculum right?
in thread [OT:] Is this Curriculum right?

The kid performed - somehow:

#!/usr/bin/env php
<?php
class Node {
  public $data;
  public $next;
}

class LinkedList {
  public  $head;

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

  public function push_back($newElement) {
    $newNode = new Node();
    $newNode->data = $newElement;
    $newNode->next = null;
    if($this->head == null) {
      $this->head = $newNode;
    } else {
      $temp = new Node();
      $temp = $this->head;
      while($temp->next != null) {
        $temp = $temp->next;
      }
      $temp->next = $newNode;
    }
  }

  public function push_at($newElement, $position) {
    $newNode = new Node();
    $newNode->data = $newElement;
    $newNode->next = null;

    if($position < 1) {
      echo "\nposition should be >= 1.";
    } else if ($position == 1) {
      $newNode->next = $this->head;
      $this->head = $newNode;
    } else {

      $temp = new Node();
      $temp = $this->head;
      for($i = 1; $i < $position-1; $i++) {
        if($temp != null) {
          $temp = $temp->next;
        }
      }

      if($temp != null) {
        $newNode->next = $temp->next;
        $temp->next = $newNode;
      } else {
        echo "\nThe previous node is null.";
      }
    }
  }

  public function PrintList() {
    $temp = new Node();
    $temp = $this->head;
    if($temp != null) {
      echo "The list contains: ";
      while($temp != null) {
        echo $temp->data." ";
        $temp = $temp->next;
      }
      echo "\n";
    } else {
      echo "The list is empty.\n";
    }
  }
};

$MyList = new LinkedList();

$MyList->push_back(10);
$MyList->push_back(20);
$MyList->push_back(30);
$MyList->PrintList();

$MyList->push_at(100, 2);
$MyList->PrintList();

$MyList->push_at(200, 1);
$MyList->PrintList();
?>

[download]

See also. Regards, Karl

«The Crux of the Biscuit is the Apostrophe»

Replies are listed 'Best First'.
Re^9: [OT:] Is this Curriculum right?
by Marshall (Canon) on Dec 06, 2021 at 19:31 UTC
    Great to hear this!

    I don't code in PHP, but this looks like it has the basics of a linked list and demonstrates understanding of the concept. It is a bit bizzare because inserts are positon based. Normally when tranversing a linked list, you are searching for something like a hash key in the case of a Perl bucket's list (search through entries that hash to the same hash value's index, looking for a match, or not of a particular key). Counting through the list to go to say the 5th thing is weird. That traversal of the list just to count them is inefficient.

    As far as Perl goes, there is no need for something like this because you would just use a Perl array. The Perl array can contain simple scalars or references to objects or whatever. One tricky bit is inserting or deleting something in the middle of the array, but Perl handles all the details via splice(). And of course also implements: push, pop, shift, unshift. So Perl array implements the functions of the SplDoublyLinkedList class and handles all the messy memory allocation and reference stuff for you.

    A C implementation of what this PHP code does (essentially an indexed array of pointers) would probably not be done via a linked list, but but rather a simple linear array of pointer to objects. For the head, instead of a single pointer to pointer to array, you would need a struct to describe: start of memory array allocation, end of memory array allocation, pointer to first sequential item within allocated memory and pointer to last sequential item within allocated array memory. Basically a block of allocated memory for the pointer array and a sequential block within that block that is actually "used" at the moment.

    To shift an element off of the top, you just adjust the pointer of the first item within allocated memory. To delete something from the bottom, you just adjust the pointer of the last item. Adding something to the top or bottom is also easy as long as there is enough "slack space" (unused "entries" within the allocated block of memory).

    Adding/deleting something in the middle is more complicated. To delete the 2nd item, you have to move the pointers to the 3rd-nth items "up" in the array. However moving blocks of memory is something that the processor can do very efficiently. The normal C function that does this is very fast and at maximum optimization levels or via an ASM subroutine, this is actually a single machine instruction! Growing the array would require memory allocation of new memory and copying the existing stuff to that new bigger array.

    Anyway, there is usually no need to implement a linked list like this PHP example in Perl because the Perl array basically does that. There probably is some outlier case, but normally that is not the situation.

[reply]

      Thank you very much for your kind reply.

      The kid performed once more. And as you might have noticed already my C skills aren’t so good. I think the code he provided isn’t really good. I fear he simply cheated it from somewhere out there. If you still have the patience take a look…

      Read more... (2 kB)

      Best regards, Karl

      «The Crux of the Biscuit is the Apostrophe»

[reply]
[d/l]
        Well the code does run.

        Of course the first thing missing is short description of what the code does.
        I had to run it to see what it did.
        like perhaps: 

        /*  Makes a linked list with new items inserted at the front.
    The list is then searched to find the last item (the item
    first inserted) and then the list is modified to remove
    all entries with data less than that item.

    The list is printed after all insertions and again after 
    the deletions.
*/

        [download]
        The code does demo some basic understanding of linked lists.
        However there is some bizarre stuff...
        reverseList() is not at all necessary (unless that was part of the problem assignment).
        If that was part of the assignment, then I would expect that there would have been a requirement to print the reversed list.

        The algorithm to delete all items less than the last one, traverses the list 3 times. Once to reverse the list to find the "last"; process list to delete items less than the "last"; reverse the list again.
        It is only necessary to traverse the list twice. Once to find the "tail". And once to "shorten" the list. reverseList() appears to be unnecessary code.

        Update: If anybody out there wants to take on a significant C freeware project, I am interested in re-coding agrep, a approximate matching version of grep. The speed of this thing is stunning. The algorithms are excellent and generated 2 Phd's. Unfortunately, the authors weren't very good C coders and the software has issues. This thing will occasionally miss matches that it should have found. The last I heard from the maintainer, a complete re-write is in order.

[reply]
[d/l]

In Section Seekers of Perl Wisdom