Proposal for "Structures_LinkedList"

» Metadata » Status
  • Category: Structures
  • Proposer: Dan Scott 
  • License: Apache License, Version 2.0
» Description

This package implements both a singly-linked list (Structures_LinkedList_Single) and doubly-linked list (Structures_LinkedList_Double) structure. A linked list offers the following advantages over a standard array() structure:

  • the ability to insert and delete key=>value nodes at arbitrary points within an existing set of nodes
  • the ability to have multiple keys with identical values

If your application normally traverses the linked list in a forward-only direction, use the singly-linked list implemented by Structures_LinkedList_Single. If, however, your application needs to traverse the list backwards, or insert nodes into the list before other nodes in the list, use the double-linked list implemented by Structures_LinkedList_Double to give your application better performance at the cost of a slightly larger memory footprint.

Structures_LinkedList_Single and Structures_LinkedList_Double implement the Iterator interface so control structures like foreach($list as $node) and while($list->next()) work as expected. You can override the key() method to enable your lists to have meaningful $key=>$value relationships in the iterator.

To use this package, derive a child class from Structures_LinkedList_DoubleNode or Structures_LinkedList_SingleNode and add data to the object. Then use the corresponding Structures_LinkedList_Double or Structures_LinkedList_Single class to access the nodes.

A good linked list implementation is critical for a proper implementation of File_MARC package, so I developed Structures_LinkedList to meet those needs. However, I believe Structures_LinkedList would be a useful addition to PEAR in general.

» Dependencies » Links
  • PHP 5
  • PEAR_Exception
» Timeline » Changelog
  • First Draft: 2006-09-03
  • Proposal: 2006-09-03
  • Call for Votes: 2006-10-02
  • Dan Scott
    [2006-09-16 05:21 UTC]


    • Separate addNode method into insertNode, appendNode, prependNode
    • Prevent current node from becoming invalid when adding a new node
    • Add a few more tests
    • Type hinting
    • Ensure this package says Apache License 2.0 everywhere, not LGPL
  • Dan Scott
    [2006-09-16 23:24 UTC]


    • Move most globals into class constants
  • Dan Scott
    [2006-09-19 17:17 UTC]

    • Name change (Structures_Linked_List to Structures_LinkedList).
    • Create a singly-linked list (Structure_LinkedList_Single in Single.php) as a base class for the doubly-linked list (Structure_LinkedList_Double in Double.php).
    • Move most globals and constants into class scope.
  • Dan Scott
    [2006-09-23 03:58 UTC]

    Switch to PEAR_Exception for error-handling

  • Dan Scott
    [2006-09-24 22:41 UTC]

    • Correct a bug in Structures_LinkedList_Single with insertNode() where $before == true
    • Add more comprehensive tests for singly-linked lists (which is why I found that bug)
    • Add well-commented examples for both singly-linked and doubly-linked lists

    Unless there are any show-stopper comments, I plan to issue a call for votes after allowing this proposal to simmer for another week or two.