PHP tutorial: Linked List


Creating a linked list by using OOP concept

In this page, you will learn to apply OOP concept in PHP to create a simple singly linked list. The linked list data structure can be used to store values dynamically. This is contrast to an array data structure that its size is fixed and cannot be easily extended. By using linked list, you can easily insert a new value to the list or delete a value from the list.

A singly linked list is made up of many nodes. Every node has two parts: data and next link. The data part stores a value of the node. The next link part is pointer to point to the next node of the linked list. The pfirst and plast are pointers that are used to point to the first node and the last node of the linked list. The pfirst pointer provides a mean to access all nodes of the linked list. The plast point allows you to access the last node so that you can append a new node easily to the linked list.

linked list

The first to create a linked list is creating a class that will be used as a template for all nodes of the linked list. The class has two members. One member is to store value of the node and another member is the next pointer to point to the next node in the linked list.

//ListNode class is the template for all nodes of the linked list.

class ListNode
{
  public $val;
  public $next;
  function ListNode($val) { $this->val=$val; $this->next = null; }

}

For this simple linked list, the operations to be performed on the nodes of the linked list are: adding a new node at a position to the linked list, delete a node from the linked list, print nodes on the screen, and get a node at a position. You can define the operations of the linked list in an interface as shown below.

interface ListOperations
{
  public function insertNode($val, $post);
  public function deleteNode($post);
  public function printList();
  public function getNodeAt($pos);

}

There two main operations of the lined list: adding a node and deleting a node. You might want to read add node to link list and delete node from the linked list to learn how to add a new node to the linked list and delete a node from the linked list.

You will need to create a new LinkedList class that will act as the linked list to store a collection of values. The LinkedList class must implement all methods defined in the interface ListOperations above.

class LinkedList implements ListOperations
{
  protected $pfirst; //points to the first element of the linked list
  protected $plast;//points to the last element of the linked list
  protected $NumItems; //records the number of nodes of the linked list
  function LinkedList() {
    $this->pfirst =null;
    $this->plast = null;
    $this->NumItems = 0;
}

//add node to the linkedlist

public function insertNode($val,$post)
{
$newNode = new ListNode($val);
if ($this->pfirst == null) //empty linked list
{
  $this->pfirst = $newNode;
  $this->plast = $newNode;
  $this->NumItems++;

}
else
{
if ($post == 1) //add new node to the beginning of th linked list
{
  $newNode->next =$this->pfirst;
  $this->pfirst =$newNode;
  $this->NumItems++;
}
//add new node to the middle position
else if($post>1 && $post<=$this->NumItems){
  $ta = $this->pfirst;
  for ($i = 1; $i < $post - 1; $i++) $ta = $ta->next;
  $newNode->next = $ta->next;
  $ta->next = $newNode;
  $this->NumItems++;
}
//append a new node
else if ($post == ($this->NumItems + 1))
{
  $this->plast->next = $newNode;
  $this->plast = $newNode;
  $this->NumItems++;
}
else
{
  echo "Invalid position";

}

}

}

//delete node from the linked list

public function deleteNode($post)
{
if ($this->pfirst == null) //empty linked list
{
  echo "Empty list";
  return;
}

if ($post == 1) //delete node from the beginning of the linked list
{
if ($this->NumItems == 1) //linked list has only one node
{
  $this->pfirst = null;
  $this->plast = null;
  $this->NumItems--;
}
else //linkelist has many nodes
{
  $temp = $this->pfirst;
  $this->pfirst =$this->pfirst->next;
  $temp = null;
  $this->NumItems--;
 }
}
//delete node at the middle position
//the last node also can be deleted
else if ($post > 1 && $post <= $this->NumItems)
{
  $ta = $this->pfirst;
  for ($i =1; $i < $post - 1;$i++) $ta = $ta->next;
  $temp = $ta->next;
  $ta->next = $temp->next;
  if ($temp->next == null) $this->plast = $ta;
   $temp = null;
   $this->NumItems--;
}
else
  echo "Invalid position";

}

//print list
public function printList()
{
  $ta =$this->pfirst;
  while ($ta != null)
{
  echo $ta->val."<br/>";
  $ta = $ta->next;
 }
}

//search node
public function getNodeAt($post){

$ta =$this->pfirst;
  $fNode=null;
  if ($post > 0 && $post <= $this->NumItems)
{
  for($i = 1; $i <$post; $i++) { $ta = $ta->next; }
  $fNode =$ta;
 }
  return $fNode;
 }

}

The is the example code to test the linked list data structured created above:

//code to test the linkedlist

$ll=new LinkedList();
$ll->insertNode(12,1);
$ll->insertNode(20,2);
$ll->insertNode(40,3);
$ll->insertNode(68,4);
$ll->deleteNode(4);
$ll->printList();
$post=2;
$fn=$ll->getNodeAt($post);
echo "The node at position ".$post." is ".$fn->val.".";

 


Comments





This website intents to provide free and high quality tutorials, examples, exercises and solutions, questions and answers of programming and scripting languages:
C, C++, C#, Java, VB.NET, Python, VBA,PHP & Mysql, SQL, JSP, ASP.NET,HTML, CSS, JQuery, JavaScript and other applications such as MS Excel, MS Access, and MS Word. However, we don't guarantee all things of the web are accurate. If you find any error, please report it then we will take actions to correct it as soon as possible.