post

SplDoublyLinkedList

Posted 05 November 2017

Before We talk about doubly linked list lets we talk about inked list. Linked list is data structure where elements are linked together. every element in the list has a at least two properties which are property is store actual data and property store pointer to the next element  in the linked list

First element in the Linked list its called Head ,  when we need find the element, we want to start to from head, if isn’t one we need we use the pointer to go next element, we continue process until the pointer of the element does not point to an element this element call tail

When creating Linked list usually, both head and tail elements are store as a meta-data for quicker access

Adding and Deleting Elements

Inserting new element is changing the pointer of the previous element let it point to the new element and pointer of the new element point to the next element

Deleting element if we want to delete element  N we want to find N-1 because  point to pointer of N-1 to N+1 and Skip N. there for delete must look up N-1 element searching through list from head element. to overcome this problem most of the linked list have an deleteAfter method where you do not point to the element you need to delete,  but to the element before that.

Sequential reads are very fast. just we can read Head element and we move until we reach the tail element. we don’t need any special method, like we needed to reach hash table sequentially , However random reads on linkedlist is so slow, because if we want to read from 6th element first we fetch head element and we have to move up to 5th element before we have found the 6th element. so it takes O(n) complexity to random read.but sequentially read takes O(1) complexity

DOUBLE-LINKED LISTS

This Nothing more than adding one more pointer to the each element to point to previous element.  this mean we can either move forward or backward. which is speedup more things

Deletion is much easier. Since we know we want to delete element N , Just move backward to find N-1 (previous ) and move forward to find N+1 (next) element. Delete operation O(1) complexity

Random reads would still not easy but, sequential read from back to front are made easy

ADVANTAGES OF USING LINKED LISTS

One of the property of linked that they don’t have an fixed size. LinkedList can be empty or can have thousand elements, no need to memory allocation in advance like hashtable . Linked list more memory efficient data structure delete and insert are very fast and also merge ,  just connect to the tail of linked list 1 and head of the Linked list 2

COUNTING ELEMENTS

Even thought lot of operation can be done with O(1) , But random reads and count take O(n) complexity, if you want to count we want to iterate through from head to tail. Because counting is such a common thing ,PHP has added meta-information inside the linked list , such as number of elements is stored in linkedlist, the counting the element in the linked list (SplDoublyLinkedList::count() ) is O(1), but merely cheating

USAGE

SplDoublyLinkedList is a perfect way to save memory. while still being to use more array functionality. main purpose of it iterate over through the elements sequential way either backward or forward. Don’t use this data structure you have planned to do  mostly random reads

NOTABLE METHODS

void SetIteratorMode(int $mode)

The setIteratorMode defines how behave when iterate through the list. following constant can be set.

IT_MODE_LIFO:   The elements are read Last in First out. in other word read backward

IT_MODE_FIFO:  The elements are read First in First out. Read forward like normal iterator. this option is default

IT_MODE_KEEP : Elements are kept when iteration. this option is default

IT_MODE_DELETE: Elements are automatically deleted when iterating

If  you want to use last in first out and delete when iterate you want to set IT_MODE_LIFO | IT_MODE_DELETE. default is IT_MODE_FIFO | IT_MODE_KEEP

$splDL = new SplDoublyLinkedList();

$splDL->push(1);
$splDL->push(2);
$splDL->push(3);
$splDL->push(4);
$splDL->push(5);

$splDL->setIteratorMode(SplDoublyLinkedList::IT_MODE_LIFO | SplDoublyLinkedList::IT_MODE_DELETE);

var_dump($splDL);

foreach ($splDL as $value) {
    echo "$value </br>";
}
var_dump($splDL);

 

Result will be

C:\wamp64\www\spl\index.php:13:
object(SplDoublyLinkedList)[1]
  private 'flags' => int 3
  private 'dllist' => 
    array (size=5)
      0 => int 1
      1 => int 2
      2 => int 3
      3 => int 4
      4 => int 5


5 
4 
3 
2 
1 


C:\wamp64\www\spl\index.php:18:
object(SplDoublyLinkedList)[1]
  private 'flags' => int 3
  private 'dllist' => 
    array (size=0)
      empty

 

mixed bottom(void)

This will return the first (head ) element of the list

mixed top (void)

This will return last(Tail) element of the list

void unshift(mixed $value)

It will be added the value top (Head) of the list. this is different from push(), where it will be added end(Tail) of the list

mixed shift(void)

shift() does opposite of unshift() it will remove an element head of the list

 

 

Leave a Reply

Your email address will not be published. Required fields are marked *