PureBasic Forums - English

Posted: **Sat Jan 06, 2007 10:53 am**

This is some code of mine that I have used to create a more flexible linked list system, like using linked lists in structures and manually setting list data
It should work just like the built in linked lists but without debugger support
it has a few added functions to improve the flexibility;

ValidateLinkedList(*This.LinkedList) ;attempts to correct any errors in the linked list
AddLinkedListToLinkedList(*This.LinkedList, *ToBeAdded.LinkedList, FreeList = #False) ;merges a linked list after the Current Element
InsertLinkedListIntoLinkedList(*This.LinkedList, *ToBeInserted.LinkedList, FreeList = #False) ;merges a Linked list before the current element

and you use these functions to create and free list

CreateLinkedList(ElementSize.l) ;create the base for a linked list
FreeLinkedList(*This.LinkedList) ;free the base (and all of it's elements) of the linked list

there no sorting for the list yet but your welcome to add them on or anything else you guys feel that useful add on for this

Code: Select all

;// Home Brewed Linked List
;// 12-22-06
;// Steven "Dreglor" Garcia

;- Structures

Structure Element
  *next.Element
  *Previous.Element
  ;Data
EndStructure

Structure LinkedList
  ElementIndex.l
  ElementCount.l
  ElementSize.l
  *First.Element
  *Current.Element
  *Last.Element
EndStructure

;- Procedures

Procedure CreateLinkedList(ElementSize.l) ;create the base for a linked list
  *New.LinkedList = AllocateMemory(SizeOf(LinkedList))
  *New\ElementCount = 0
  *New\ElementSize = ElementSize
  *New\First = #Null
  *New\Current = #Null
  *New\Last = #Null
  ProcedureReturn *New
EndProcedure

Procedure FreeLinkedList(*This.LinkedList) ;free the base (and all of it's elements) of the linked list
  If *First <> #Null
    *This\Current = *This\First
    Repeat
      NextPointer = *This\Current\Next
      FreeMemory(*This\Current)
      *This\Current = NextPointer
    Until NextPointer = #Null
  EndIf
  FreeMemory(*This)
EndProcedure

Procedure InsertElementIntoLinkedList(*This.LinkedList) ;inserts a new element before the current element
  *New.Element = AllocateMemory(*This\ElementSize + 8)
  *New\Next = *This\Current
  *New\Previous = *This\Current\Previous
  *This\Current = *New
  *This\ElementCount = *This\ElementCount + 1
  ProcedureReturn *New
EndProcedure

Procedure AddElementToLinkedList(*This.LinkedList) ; adds a new element after the current element
  *New.Element = AllocateMemory(*This\ElementSize + 8)
  *New\Next = *This\Current\Next
  *New\Previous = *This\Current
  *This\Current = *New
  *This\ElementCount + 1
  *This\ElementIndex + 1
  ProcedureReturn *New
EndProcedure

Procedure DeleteElementFromLinkedList(*This.LinkedList, flags.b) ;deletes the current element
  ElementToDelete = *This\Current
  *This\Current\Previous\Next = *This\Current\Next
  If flags <> #Null
    *This\ElementIndex + 1
    *This\Current = *This\Current\Next
  Else
    *This\ElementIndex - 1
    *This\Current = *This\Current\Previous
  EndIf
  *This\ElementCount - 1
  FreeMemory(ElementToDelete)
  ProcedureReturn *This\Current
EndProcedure

Procedure GetElementFromLinkedList(*This.LinkedList) ;gets teh pointer to the direct data for the element
  ProcedureReturn *This\Current + 8
EndProcedure

Procedure SelectElementFromLinkedList(*This.LinkedList, index.l) ;selects an element via it's index
  If index > *This\ElementCount
    ProcedureReturn #Null
  EndIf
  *This\Current = *This\First
  For Element = 0 To index
    *This\Current = *This\Current\Next
  Next
  *This\ElementIndex = index
  ProcedureReturn *This\Current
EndProcedure

Procedure NextElementInLinkedList(*This.LinkedList) ;moves the current element to the next element
  If *This\Current = #Null
    *This\Current = *This\First
  Else
    *This\Current = *This\Current\Next
  EndIf
  *This\ElementIndex + 1
  ProcedureReturn *This\Current
EndProcedure

Procedure PreviousElementInLinkedList(*This.LinkedList) ;moves the current element to the next element
  If *This\Current\Previous = #Null
    ProcedureReturn #Null
  EndIf
  *This\Current = *This\Current\Previous
  *This\ElementIndex - 1
  ProcedureReturn *This\Current
EndProcedure

Procedure FirstElementInLinkedList(*This.LinkedList) ;moves the current element to the first element
  *This\Current = *This\First
  *This\ElementIndex = 0
  ProcedureReturn *This\Current
EndProcedure
  
Procedure LastElementInLinkedList(*This.LinkedList) ;moves the current element to the Last element
  *This\Current = *This\Last
  *This\ElementIndex = *This\ElementCount
  ProcedureReturn *This\Current
EndProcedure

Procedure SwapElementInLinkedList(*ElementOne.Element, *ElementTwo.Element)
  Swap *ElementOne\Next, *ElementTwo\Next
  Swap *ElementOne\Previous, *ElementTwo\Previous
EndProcedure

Procedure IndexLinkedList(*This.LinkedList) ;returns the current location or index of the of the linked list
  ProcedureReturn *This\ElementIndex
EndProcedure
  
Procedure CountElementsLinkedList(*This.LinkedList) ;returns the number of elements in the current linked list
  ProcedureReturn *This\ElementCount
EndProcedure

Procedure ClearLinkedList(*This.LinkedList) ;clears (and free's the allocated data) of the linked list
  *This\Current = *This\First
  Repeat
    NextPointer = *This\Current\Next
    FreeMemory(*This\Current)
    *This\Current = NextPointer
  Until NextPointer = #Null
  *This\First = #Null
  *This\Last = #Null
  *This\ElementCount = 0
  *This\ElementIndex = -1
EndProcedure

Procedure ResetLinkedList(*This.LinkedList) ;changes the current element to NULL
  *This\ElementIndex = -1
  *This\Current = #Null
EndProcedure

Procedure ChangeCurrentElementInLinkedList(*This.LinkedList, *ChangeTo.Element) ;change the current element to a Element Pointer
  OldElement = *This\Current
  OldIndex = *This\ElementIndex
  *This\Current = *This\First
  *This\ElementIndex = 1
  Repeat
    NextPointer = *This\Current\Next
    If *This\Current = *ChangeTo
      ProcedureReturn *This\Current
    EndIf
    *This\Current = *This\Current\Next
    *This\ElementIndex + 1
  Until *This\Current
  
  *This\Current = OldElement
  *This\ElementIndex = OldIndex
  ProcedureReturn #Null
EndProcedure

Procedure InsertLinkedListIntoLinkedList(*This.LinkedList, *ToBeInserted.LinkedList, FreeList = #False) ;merges a Linked list before the current element
  *ToBeInserted\First\Previous = *This\Current\Previous
  *ToBeInserted\First\Next = *This\Current
  *This\Current\Previous = *ToBeInserted\First
  *This\Current = *ToBeInserted\First
  *This\ElementCount + *ToBeInserted\ElementCount
  
  If FreeList = #True
    FreeMemory(ToBeInserted)
  EndIf
  
  ProcedureReturn *This\Current
EndProcedure

Procedure AddLinkedListToLinkedList(*This.LinkedList, *ToBeAdded.LinkedList, FreeList = #False) ;merges a linked list after the Current Element
  *ToBeAdded\First\Previous = *This\Current
  *ToBeAdded\First\Next = *This\Current\Next
  *This\Current\Next = *ToBeAdded\First
  *This\Current = *ToBeAdded\First
  *This\ElementCount + *ToBeAdded\ElementCount
  
  If FreeList = #True
    FreeMemory(ToBeInserted)
  EndIf
  
  ProcedureReturn *This\Current
EndProcedure

Procedure ValidateLinkedList(*This.LinkedList) ;attempts to correct any errors in the linked list
  ;corrects one-way links
  ;corrects Null First or Last elements (if possible)
  ;corrects element index
  ;corrects element count
  If *This\First = #Null
    If *This\Last = #Null
      If *This\Current = #Null
        *This\Last = #Null
        *This\Current = #Null
        *This\ElementIndex = -1
        *This\ElementCount = 0
      Else
        Repeat
          LastElement = *This\Current
          *This\Current = *This\Current\Previous
          *This\Current\Next = *This\Current
        Until *This\Current\Previous = #Null
        *This\First = *This\Current
        Repeat
          LastElement = *This\Current
          *This\Current = *This\Current\Next
          *This\Current\Previous = LastElement
          *This\ElementCount + 1
        Until *This\Current\Next = #Null
        *This\Last = *This\Current
        *This\Current = #Null
        *This\ElementIndex = 0
      EndIf
    Else
      *This\Current = *This\Last
      Repeat
        LastElement = *This\Current
        *This\Current = *This\Current\Previous
        *This\Current\Next = *This\Current
        *This\ElementCount + 1
      Until *This\Current\Previous = #Null
      *This\First = *This\Current
      *This\Current = #Null
      *This\ElementIndex = 0
    EndIf
  Else
    *This\Current = *This\First
    *This\ElementCount = 0
    Repeat
      LastElement = *This\Current
      *This\Current = *This\Current\Next
      *This\Current\Previous = LastElement
      *This\ElementCount + 1
    Until *This\Current\Next = #Null
    *This\Last = *This\Current
    *This\Current = #Null
    *This\ElementIndex = 0
  EndIf
EndProcedure

PureBasic Forums - English

Homebrewed Linked List

Homebrewed Linked List