Another linked list

Post your FreeBASIC tips and tricks here. Please don’t post your code without including an explanation.
notthecheatr
Posts: 1759
Joined: May 23, 2007 21:52
Location: Cut Bank, MT
Contact:

Another linked list

Postby notthecheatr » Jan 08, 2008 0:03

Inspired by KristopherWindsor, I wrote my own linked list object. It should be thread-safe (I haven't tested it though) and it has all the functions you would need - addItem, removeItem, insertItem, getItem, removeAll, and numItems. The names are self explanatory; an example is given. I've also tried to write the code so it's as readable for newbies as possible, and it's especially very well commented in the methods. Stores a list of uIntegers (since they're the same size and no conversions will be made, you can store pointers instead if you Cast them).

linkedList.bas:

Code: Select all

''
''
'' notthecheatr linked list object
''
''

'Do whatever you want with it, I wouldn't mind credit but it's easy so
'I don't demand it by any means.  If you do use it you do so at your
'own risk, I cannot be responsible for anything that happens as a result
'of, or associated with, using this object.


'These allow you to specify a different data type for the list items (for example, Any Ptr).
'Note that I would not recommend using String here, it probably wouldn't even compile but it certainly
'wouldn't be wise given the way the data is stored.  You can use Ptrs though, if you like.
#define LIST_DATA_TYPE uInteger
#define DEFAULT_LIST_DATA 0


'Internally used list item (never used or accessed directly by the parent/host program)
Type _list_item
  As list_DATA_TYPE _data
  As _list_item Ptr _next
End Type

Type linkedList
  Public:
    Declare Constructor ()
    Declare Destructor ()

    Declare Function addItem (item As list_DATA_TYPE) As uInteger
    Declare Function getItem (index As uInteger) As list_DATA_TYPE
    Declare Sub insertItem (item As list_DATA_TYPE, index As uInteger = 0)
    Declare Sub moveItem (curIdx As uInteger = 0, nextIdx As uInteger = 0)
    Declare Sub removeItem (index As uInteger)
    Declare Sub removeAll ()
    Declare Sub swapItems (index1 As uInteger, index2 As uInteger = 0)

    Declare Property numItems () As uInteger

  Private:
    As _list_item Ptr _first
    As _list_item Ptr _last

    As uInteger _num_items

    As Any Ptr _info_mutex

    As uInteger _err_val
End Type

Constructor linkedList
  this._num_items = 0
  this._info_mutex = MutexCreate()
  this._err_val = 0
End Constructor

Destructor linkedList
  this.removeAll
  this._err_val = Not 0
  MutexDestroy(this._info_mutex)
  this._info_mutex = 0
End Destructor

Function linkedList.addItem (item As list_DATA_TYPE = DEFAULT_list_DATA) As uInteger
Dim As _list_item Ptr tmpItem

  'Lock the mutex for thread safety
  MutexLock(this._info_mutex)

  'If it's the first item in the list
  If this._num_items = 0 Then
    'Allocate space for it
    this._first = Allocate(SizeOf(_list_item))
    'And the first will be the same as the last
    this._last = this._first
    'And the next item is also the same
    this._first->_next = this._first
    'Add the data
    this._first->_data = item
    'Increment the items count
    this._num_items += 1
   
    'Unlock the mutex before we leave
    MutexUnlock(this._info_mutex)
    'Return the item position in the list
    Return 0
  Else
    'Start at the last item
    tmpItem = this._last
    'Add the *next* item
    tmpItem->_next = Allocate(SizeOf(_list_item))
    'And it's also the last item
    this._last = tmpItem->_next

   
    this._last->_next = this._first
   
    'Add in the actual data
    this._last->_data = item
    'Increment the item counter
    this._num_items += 1
   
    'Unlock the mutex before we leave
    MutexUnlock(this._info_mutex)
    'And return the number of items
    Return this._num_items-1
  End If
End Function

Function linkedList.getItem (index As uInteger) As list_DATA_TYPE
'Starting at the first list item
Dim As _list_item Ptr tmpItem = this._first

  'If there are no items in the list, return 0
  If this._num_items = 0 Then Return DEFAULT_list_DATA

  'Lock the mutex
  MutexLock(this._info_mutex)

  'We're going to go through the items until we get to the one intended
  Do Until index = 0
    'Go to the next one
    tmpItem = tmpItem->_next
    'And decrement the index so when we get to the right one it will be 0
    index -= 1
  Loop

 'Unlock the mutex
  MutexUnlock(this._info_mutex)

  'Return the data from that item
  Return tmpItem->_data
End Function

Sub linkedList.moveItem (curIdx As uInteger = 0, nextIdx As uInteger = 0)
Dim As list_DATA_TYPE tmpItem

  If curIdx >= this._num_items Then curIdx = this._num_items-1
  If nextIdx >= this._num_items Then nextIdx = this._num_items-1
  If curIdx = nextIdx Then Exit Sub

  tmpItem = this.getItem(curIdx)
  this.removeItem(curIdx)
  this.insertItem(tmpItem, nextIdx)
End Sub

Sub linkedList.insertItem (item As list_DATA_TYPE = DEFAULT_list_DATA, index As uInteger = 0)
'Starting at the first list item
Dim As _list_item Ptr tmpItem = this._first
Dim As _list_item Ptr tmpItem2

   'Lock the mutex for thread safety
  MutexLock(this._info_mutex)

  If this._num_items = 0 Then
    this._err_val = 1
    Exit Sub
  End If

  'If we're inserting it at the first position
  If index = 0 Then
    'Increment the item counter
    this._num_items += 1
    'Create the new item
    this._first = Allocate(SizeOf(_list_item))
    'Set its next to the former first
    this._first->_next = tmpItem
   
    this._last->_next = this._first
   
    'And add the data
    this._first->_data = item
   
  Elseif index = this._num_items Then
    'Increment the item counter
    this._num_items += 1
    'Save the old last item
    tmpItem = this._last
    'Create the new item at the last position
    this._last = Allocate(SizeOf(_list_item))
    'Set the next item from the old last item to the new last item
    tmpItem->_next = this._last
    'Set the data in the new last item
    this._last->_data = item
    'And set the next item of the last item to the first item
    this._last->_next = this._first
   
    this._last->_next = this._first
   
  Else
    'First decrease the index once
    index -= 1

    'We're going to go through the items until we get to the one intended
    Do Until index = 0
      'Go to the next one
      tmpItem = tmpItem->_next
      'And decrement the index so when we get to the right one it will be 0
      index -= 1
    Loop
    'Save the old next item
    tmpItem2 = tmpItem->_next
    'Create the new
    tmpItem->_next = Allocate(SizeOf(_list_item))
    'And set its next to the old one
    tmpItem->_next->_next = tmpItem2
    'And add the data
    tmpItem->_next->_data = item
    'Increment the item counter
    this._num_items += 1
 
  End If

  'Unlock the mutex
  MutexUnlock(this._info_mutex)
End Sub

Sub linkedList.removeItem (index As uInteger)
'Starting at the first list item
Dim As _list_item Ptr tmpItem = this._first
Dim As _list_item Ptr tmpItem2

   'Lock the mutex for thread safety
  MutexLock(this._info_mutex)

  If this._num_items = 0 Then
    this._err_val = 1
    Exit Sub
  End If

  'If we're removing the first item...
  If index = 0 Then
     'Set the correct values, then delete the first item
    this._first = this._first->_next
    this._last->_next = this._first
    DeAllocate(tmpItem)
   
  'If we're removing the last item...
  ElseIf index = this._num_items-1 Then
     'Set all the proper values, then delete the former last item
    tmpItem = this._last
    this._last->_next = this._first
   
    DeAllocate(tmpItem)
  Else
    index -= 1
    Do Until index = 0
      tmpItem = tmpItem->_next
      index -= 1
    'The one before the one we're removing
    Loop
    'Save the one *after* the one being removed
    tmpItem2 = tmpItem->_next->_next
    'Remove the item
    DeAllocate(tmpItem->_next)
    'And set the next one to the one we saved
    tmpItem->_next = tmpItem2
  End If
  'Decrement the item counter
  this._num_items -= 1
 
 

  'Unlock the mutex
  MutexUnlock(this._info_mutex)
End Sub

Sub linkedList.removeAll ()

  Do Until this._num_items = 0
    this.removeItem(0)
  Loop
End Sub

Property linkedList.numItems() As uInteger
  Return this._num_items
End Property

Sub linkedList.swapItems (index1 As uInteger, index2 As uInteger = 0)
Dim As _list_item Ptr tmpItem1 = this._first, tmpItem2 = this._first

  'Don't bother if there aren't any items to swap...
  If this._num_items = 0 Then Exit Sub
  '...or if either index is beyond the range of valid indexes.
  If index1 > this._num_items-1 Or index2 > this._num_items-1 Then Exit Sub


  'If the indexes are the same then don't bother
  If index1 = index2 Then Exit Sub

  'Lock the mutex for thread safety.
  MutexLock(this._info_mutex)


  'Make sure index1 comes before index2
  If index2 < index1 Then
    Swap index2, index1
  End If


  'Subtract the first from the second since when we search for the second we'll be starting from the first
  index2 -= index1
  'Now starting with the first, go to the next item until we get to the correct one (when index1 = 0)
  Do Until index1 = 0
    tmpItem1 = tmpItem1->_next
    index1 -= 1
  Loop
  'Now on the second, we start from where we left off...
  tmpItem2 = tmpItem1
  '... and go to the next item until we get to the correct one (when index2 = 0)
  Do Until index2 = 0
    tmpItem2 = tmpItem2->_next
    index2 -= 1
  Loop
  'And swap the data in them
  Swap tmpItem1->_data, tmpItem2->_data


  'Unlock the mutex
  MutexUnlock(this._info_mutex)
End Sub


test.bas:

Code: Select all

#Include Once "linkedList.bas"

Dim As linkedList myList

myList.addItem(1)
myList.addItem(2)
myList.addItem(3)

Print "Linked list demo:"
Print "  Items in list:  " + Str(myList.numItems)
Print "  Item #1:  " + Str(myList.getItem(0))
Print "  Item #2:  " + Str(myList.getItem(1))
Print "  Item #3:  " + Str(myList.getItem(2))

myList.removeItem(1)
Print "Removed the second item.  Now:"
Print "  Items in list:  " + Str(myList.numItems)
Print "  Item #1:  " + Str(myList.getItem(0))
Print "  Item #2:  " + Str(myList.getItem(1))

myList.insertItem(6, 1)
Print "Inserted 6 between the first and second items.  Now:"
Print "  Items in list:  " + Str(myList.numItems)
Print "  Item #1:  " + Str(myList.getItem(0))
Print "  Item #2:  " + Str(myList.getItem(1))
Print "  Item #3:  " + Str(myList.getItem(2))

myList.swapItems(0,2)
Print "Swapped first and third items.  Now:"
Print "  Items in list:  " + Str(myList.numItems)
Print "  Item #1:  " + Str(myList.getItem(0))
Print "  Item #2:  " + Str(myList.getItem(1))
Print "  Item #3:  " + Str(myList.getItem(2))

myList.removeAll
Print "Removed All.  Now:"
Print "  Items in list:  " + Str(myList.numItems)

Sleep


Note: in the latest update the parameters in insertItem have been switched. The index to insert now defaults to 0, so if you need to insert at the beginning of the list you don't need to specify a second argument. The second argument of swapItems also defaults to 0, so if you want to swap any item with the first item in the list you only need to specify the item that isn't the first item in the list, and the second argument you can leave out.

If you like this you might find my double-linked list object useful also.
Last edited by notthecheatr on Feb 28, 2008 23:48, edited 5 times in total.
DaveUnit
Posts: 239
Joined: Apr 20, 2006 15:47
Location: Central MA
Contact:

Postby DaveUnit » Jan 08, 2008 0:25

hey nice, I was just working on my own linked list but now that you posted this, f that! :P
notthecheatr
Posts: 1759
Joined: May 23, 2007 21:52
Location: Cut Bank, MT
Contact:

Postby notthecheatr » Jan 08, 2008 0:41

You're welcome! Not hard to do at all, but it did take a bit of time. Figured I may as well share my results with the community. Glad I was just in time to stop you from doing it all yourself :D

Incidentally, I think fbext also has a list object. Which of course doesn't discourage me from writing my own, it's good practice after all :D
DaveUnit
Posts: 239
Joined: Apr 20, 2006 15:47
Location: Central MA
Contact:

Postby DaveUnit » Jan 08, 2008 0:45

fbext has one? I looked a little while ago and didn't see one, maybe I'm just oblivious. But regardless, your code should be fine for my needs.
maybe add a swap function? hell, maybe I can add it myself, shouldn't be too hard. With that you could sort lists a lot easier.
DaveUnit
Posts: 239
Joined: Apr 20, 2006 15:47
Location: Central MA
Contact:

Postby DaveUnit » Jan 08, 2008 1:03

Made a swap sub and a function that returns a pointer to the list item rather than just data.

add these declares:

Code: Select all

declare function getListItem(index as uinteger) as _list_item ptr
declare sub swapItems(index1 as uinteger, index2 as uinteger)


add these functions:

Code: Select all

function linkedList.getListItem(index as uinteger) as _list_item ptr
   'Starting at the first list item
   Dim As _list_item Ptr tmpItem = this._first

  'If there are no items in the list, return 0
  If this._num_items = 0 Then Return 0

  'Lock the mutex
  MutexLock(this._info_mutex)

  'We're going to go through the items until we get to the one intended
  Do Until index = 0
    'Go to the next one
    tmpItem = tmpItem->_next
    'And decrement the index so when we get to the right one it will be 0
    index -= 1
  Loop

 'Unlock the mutex
  MutexUnlock(this._info_mutex)

  'Return the data from that item
  Return tmpItem
end function

sub linkedList.swapItems(index1 as uinteger, index2 as uinteger)
   dim as _list_item ptr item1 = getListItem(index1), item2 = getListItem(index2)
   
   swap item1->_data, item2->_data
end sub


your test with added swap test:

Code: Select all

#include "list.bas"

Dim As linkedList myList

'addItem can also be used as a function;  it will return the index of the
'item added if you use it this way.  It only takes one argument, the
'item to be added, which is a uInteger (you can easily store pointers
'this way, too)
myList.addItem(1)
myList.addItem(2)
myList.addItem(3)

Print "Items in list:  " + Str(myList.numItems)
Print "Item #1:  " + Str(myList.getItem(0))
Print "Item #2:  " + Str(myList.getItem(1))
Print "Item #3:  " + Str(myList.getItem(2))

'removeItem removes the item with the index specified
myList.RemoveItem(0)
Print "Removed the first item.  Now:"
Print "  Items in list:  " + Str(myList.numItems)
Print "  Item #1:  " + Str(myList.getItem(0))
Print "  Item #2:  " + Str(myList.getItem(1))

'insertItem inserts the item, in this case 6, at the index specified, in
'this case 1.
myList.insertItem(1, 6)
Print "Inserted 6 between the first and second items.  Now:"
Print "  Items in list:  " + Str(myList.numItems)
Print "  Item #1:  " + Str(myList.getItem(0))
Print "  Item #2:  " + Str(myList.getItem(1))
Print "  Item #3:  " + Str(myList.getItem(2))

myList.swapItems(0, 2)
print "Swapped first and last items.  Now:"
Print "  Items in list:  " + Str(myList.numItems)
Print "  Item #1:  " + Str(myList.getItem(0))
Print "  Item #2:  " + Str(myList.getItem(1))
Print "  Item #3:  " + Str(myList.getItem(2))


'removeAll, of course, removes all the items in the list.
myList.RemoveAll
Print "Removed All.  Now:"
Print "  Items in list:  " + Str(myList.numItems)

sleep


the code formatting here kinda screwed with how I indent my code. :(
notthecheatr
Posts: 1759
Joined: May 23, 2007 21:52
Location: Cut Bank, MT
Contact:

Postby notthecheatr » Jan 08, 2008 2:33

Right, sorry about that... I actually realized later that I needed to add one. I won't have time to test this tonight, but this should work:

Code: Select all

Sub linkedList.swap (index1 As uInteger, index2 As uInteger)
Dim As uInteger item1, item2
  item1 = this.getItem(index1)
  item2 = this.getItem(index2)
  this.removeItem(index1)
  this.removeItem(index2)
  this.insertItem(index1, item2)
  this.insertItem(index2, item1)
End Sub


You may have to subtract or add 1 to one or both of the indexes before inserting, or something similar, but other than that this should work. Of course, it's probably faster just to swap values rather than remove and insert, so I'll get that part done tomorrow.
DaveUnit
Posts: 239
Joined: Apr 20, 2006 15:47
Location: Central MA
Contact:

Postby DaveUnit » Jan 08, 2008 11:34

yeah, that's probably a better way to do it since people can't get their hands on the _list_items like in mine. Although, my getListItem function could just be made private and problem solved.
notthecheatr
Posts: 1759
Joined: May 23, 2007 21:52
Location: Cut Bank, MT
Contact:

Postby notthecheatr » Jan 08, 2008 16:59

Updated January 8, 2008

A swapItems method has been implemented, and it should be as efficient as possible (without, for example, using assembly... even then I'm not sure you could make it much faster). It takes two indexes, searches for the lowest one, then finds the other one starting from that point. Once it has the two items, it simply swaps the data in them, without destroying or re-creating either item.

And now you can specify a different data type than uInteger for the list items. The first two lines

Code: Select all

#define LIST_DATA_TYPE uInteger
#define DEFAULT_LIST_DATA 0


Let you choose the default data type and the default value to be returned if you specify an invalid index or the like. The most likely choice will be Any Ptrs... this way you can use the list object to create a list of any other data type, UDTs for example. The only item that would not be safe to use is strings, because of the way they are done. You could probably do static strings (yuo'd need to make DEFAULT_LIST_DATA "" instead of 0) but I wouldn't trust even those. Arrays should be usable, but not dynamic ones (since it's inside a UDT, and dynamic arrays may not be inside UDTs).
DaveUnit
Posts: 239
Joined: Apr 20, 2006 15:47
Location: Central MA
Contact:

Postby DaveUnit » Jan 08, 2008 17:11

nice job, man. A lot nicer and safer than my quick fix. I like that now I can use any ptrs. gotta love #defines.
thanks a lot.
notthecheatr
Posts: 1759
Joined: May 23, 2007 21:52
Location: Cut Bank, MT
Contact:

Postby notthecheatr » Jan 08, 2008 18:04

Yep. I think I'll write a bunch of other data structures too, this is fun. I'm on a roll now!
DaveUnit
Posts: 239
Joined: Apr 20, 2006 15:47
Location: Central MA
Contact:

Postby DaveUnit » Feb 28, 2008 23:11

I know this topic is dead and all. But I really liked this list, very easy to use, but I'm getting a seg fault when I remove an item that's not the first or last item. if you change your example to remove one of item index 1 instead of 0 and run with gdb it will seg fault.

edit:
found fix.
if you replace...

Code: Select all

    index -= 1
    Do
      tmpItem = tmpItem->_next
      index -= 1
    'The one before the one we're removing
    Loop Until index = 1

... in the removeItem sub to...

Code: Select all

    for i as integer = 1 to index - 1
       tmpItem = tmpItem->_next
    next

it will work and not seg fault.
notthecheatr
Posts: 1759
Joined: May 23, 2007 21:52
Location: Cut Bank, MT
Contact:

Postby notthecheatr » Feb 28, 2008 23:33

I just fixed it in the post before you made your edit :D

I actually found it a couple weeks ago while trying to use the linkedList. So it's fixed. As far as I can tell now, it works.
DaveUnit
Posts: 239
Joined: Apr 20, 2006 15:47
Location: Central MA
Contact:

Postby DaveUnit » Feb 28, 2008 23:39

haha. well I'm still proud of myself for fixing it too! :P
I was wondering, do you think you add some sort of sequential access to the list.
like if I have 500 objects to read, using getItem is going to start at the beginning of the list and not the last item searched, so when I reach 500, getItem still has to go allll the way the way through the list again from the beginning.
maybe if you added something like lastItem that keeps track of the last item that you got and maybe a getNextItem function. Because right now I use the list to hold map objects, so if there are a lot on screen having to keep starting from the beginning every time I need a sprite is making my drawing loop go slower.
notthecheatr
Posts: 1759
Joined: May 23, 2007 21:52
Location: Cut Bank, MT
Contact:

Postby notthecheatr » Feb 28, 2008 23:45

I've added this to the double-linked list, it probably wouldn't be too difficult to add the same thing to this one (you could probably take the functions already there and use them - you'll just have to leave out the goPrevious and getPrevious functions, since obviously they won't work).

Return to “Tips and Tricks”

Who is online

Users browsing this forum: Bing [Bot] and 2 guests