- Home

   - Forums

   - Programming

   - Development

   - Projects

   - Articles

   - Tutorials

   - Snippets

   - Synapse Engine

 

  - Single Linked List - Single linked lists are a data structure that implements items that form a list based on their

    relationships. The term single linked list comes from the property that each item in the list only points to the next

    item in the list. This is a single link that connects these two items. The link between these two items can only be

    traveled in one direction.

   

    The items that are contained in the list are held in objects called 'Nodes'. These nodes hold a link to the data that

    is the item in the list. Below illustrates the relationship between Nodes, their data and each other.

 

 

The image represents the pointers of a single linked list. Each node has

a pointer to the next node in the list and and pointer to the data it holds.

 

     Having each node in the list only have to maintain a pointer to its next node the list can be held in a single variable.

    This node is called the head node. This is the beginning of the list. Every item in the list can be found using the head

    node. Some single linked list implementations also include the use of a tail pointer. The cost of this varies for different

    algorithms. Maintaining a tail pointer adds costs to other simpler algorithms however it does provide a very simple

    means of implementing an add last algorithm.

 

 

    Breaking List Relationships - Breaking a link between nodes cuts the list into two separate lists, however if

    each side is not accounted for they will become broken. Representing this concept is easily done with blocks and

    string. Below is an example of blocks 'A', 'B' 'C' and 'D' connected together by string. The first block is secured

    to the head.

 

       

The images above symbolize the single linked list concept through the relationships between

blocks connected together with string to maintain the blocks from falling

 

    The first image represents a fully linked list. The blocks are secured together by the link of the node before it. If a

    link is removed ( second figure ) the list becomes broken. The link from block 'B' was set to null this represents

    the block 'C' being removed from the string connected to block 'B'. This results in blocks 'C' and 'D' falling off of the

    list. Note that theoretically block 'C' still contains its link to block 'D' however there is no way to reference block 'C'

    unless a variable is holding a reference to block 'C' before the link from block 'B' to 'C' was destroyed. The last figure

    represents an empty list. The head pointer is null and does not contain any blocks. The blocks are now unreferenced

    garbage.

 

 

 

 

 

 

 

 

 

       
 - About Brokendust - I am a computer science major with a minor in mathematics. My interests include programming, 3d Design and application development. I document everything I do and write articles explaining things both as a way to remember what I have learned before and as way to show others how to accomplish things. I do not post tutorials that do not live up to my expectations. Each article is toughly revised to be quality work.

 

- Current Projects -

3D MGR

ABLL

PE