[Published on GitHub] LinkedList Class (Fully implemented)

[ivanseidel]

Hi folks,

I have published my LinkedList Class on GitHub. It's REALLY usefull for all kinds of libraries and projects.

Features that are implemented:

• LinkedList<T>::LinkedList() - Constructor.


• LinkedList<T>::~LinkedList() - Destructor. Clear Nodes to minimize memory.


• int LinkedList<T>::size() - Returns the current size of the list.


• bool LinkedList<T>::add(T) - Add element T at the END of the list.


• bool LinkedList<T>::add(int index, T) - Add element T at index of the list.


• bool LinkedList<T>::unshift(T) - Add element T at the BEGINNING of the list.


• bool LinkedList<T>::set(int index, T) - Set the element at index to T.


• T LinkedList<T>::remove(int index) - Remove element at index. Return the removed element.


• T LinkedList<T>::pop() - Remove the LAST element. Return the removed element.


• T LinkedList<T>::shift() - Remove the FIRST element. Return the removed element.


• T LinkedList<T>::get(int index) - Return the element at index.


• void LinkedList<T>::clear() - Removes all elements.

For more information, and Latest releases go to https://github.com/ivanseidel/LinkedList

Fell free to commit new changes and use it.

Ivan

[robtillaart]

Thanks for sharing,

[ivanseidel]

I'm happy to help...

[ivanseidel]

-------- NEW VERSION --------

1.1 (2013-08-03): Cache implemented. Getting subsequent objects is now O(N). Before, O(N^2).


We made a simple test, reading 1000 sequently elements 100 times and took the time needed to do it:

With previous version (Without caching system), took about 45000 miliseconds
With the new version (with a simple caching system), took 750 miliseconds

Update now and enjoy =)

[robtillaart]

Have you tried to implement skiplists ?
skiplists are fast dynamic datastructures, use 2n nodes for n values, and have an on average accestime of (Log(n))

- http://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-046j-introduction-to-algorithms-sma-5503-fall-2005/video-lectures/lecture-12-skip-lists/ -

fun structure to implement!

[ivanseidel]

Have you tried to implement skiplists ?
skiplists are fast dynamic datastructures, use 2n nodes for n values, and have an on average accestime of (Log(n))

That's cool! I had one idea like that, but didn't know it had a name...

If you want to, you can doit. If it's easy to use, then I can merge with the existing one =)

Thanks for the idea.

Ivan

[Molex1701]

Hello,
  It looks like this is suppose to work with our own Class but when I try it, LinkedList gives a lot of errors.  Looks to be very useful, I hope I can use it.  Thanks.

Code: [Select]

#include <LinkedList.h>

LinkedList<int> myLinkedList = LinkedList<int>();
class test
{
public:
  test();
  int x;
};
test::test(){}

LinkedList<test> *myLinkedList2 = LinkedList<test>();
void setup()
{
}
void loop()
{
}


Code: [Select]

sketch_feb03a.ino: In constructor 'ListNode<test>::ListNode()':
C:\Users\Richard\Documents\Arduino\libraries\LinkedList/LinkedList.h:18:   instantiated from 'bool LinkedList<T>::add(int, T) [with T = test]'
sketch_feb03a.ino:17:   instantiated from here
sketch_feb03a:9: error: 'test::test()' is private
C:\Users\Richard\Documents\Arduino\libraries\LinkedList/LinkedList.h:18: error: within this context
C:\Users\Richard\Documents\Arduino\libraries\LinkedList/LinkedList.h: In member function 'bool LinkedList<T>::add(int, T) [with T = test]':
C:\Users\Richard\Documents\Arduino\libraries\LinkedList/LinkedList.h:175: note: synthesized method 'ListNode<test>::ListNode()' first required here
C:\Users\Richard\Documents\Arduino\libraries\LinkedList/LinkedList.h: In member function 'T LinkedList<T>::remove(int) [with T = test]':
sketch_feb03a.ino:17:   instantiated from here
C:\Users\Richard\Documents\Arduino\libraries\LinkedList/LinkedList.h:286: error: conversion from 'bool' to non-scalar type 'test' requested
sketch_feb03a.ino:17:   instantiated from here
C:\Users\Richard\Documents\Arduino\libraries\LinkedList/LinkedList.h:301: error: conversion from 'bool' to non-scalar type 'test' requested
C:\Users\Richard\Documents\Arduino\libraries\LinkedList/LinkedList.h: In member function 'T LinkedList<T>::pop() [with T = test]':
sketch_feb03a.ino:17:   instantiated from here
C:\Users\Richard\Documents\Arduino\libraries\LinkedList/LinkedList.h:239: error: conversion from 'bool' to non-scalar type 'test' requested
C:\Users\Richard\Documents\Arduino\libraries\LinkedList/LinkedList.h: In member function 'T LinkedList<T>::shift() [with T = test]':
sketch_feb03a.ino:17:   instantiated from here
C:\Users\Richard\Documents\Arduino\libraries\LinkedList/LinkedList.h:265: error: conversion from 'bool' to non-scalar type 'test' requested
C:\Users\Richard\Documents\Arduino\libraries\LinkedList/LinkedList.h: In member function 'T LinkedList<T>::get(int, bool) [with T = test]':
sketch_feb03a.ino:17:   instantiated from here
C:\Users\Richard\Documents\Arduino\libraries\LinkedList/LinkedList.h:308: error: no match for ternary 'operator?:' in '(tmp != 0u) ? tmp->ListNode<test>::data : false'


I've tried with  LinkedList<int> *myLinkedList = LinkedList<int>(); then I just get a message about converting.

[ivanseidel]

Hi!
Take a look at pointers and objects by instance to understand it better. But in your case you are trying to instantiate a poiinter linked list with an instance.object...

Also, when working with the list within different scope (loop, void, classes...), its a good practice to instantiate as a poiter. (If there will be lots of classes, its a good idea to delete it after you dont need it anymore).

What i use to do is:

Code: [Select]

LinkedList<mytype> *myList;

void setup{
  myList = new LinkedList<mytype>();
}

// In your code
myList->add(....);

[Molex1701]

Hi,
  Thanks for fast response.  Unfortunately that doesn't work either.  Same errors.   Computers have really been troublesome for me lately. lol.

[pYro_65]

Hi, @Molex1701 there may be a requirement for your class to implement certain operators as your class is not a POD ( you have a default constructor ). But there seems to be more problems, I believe there is a slight bug.

@ivanseidel, your remove function assumes that bool can be converted to any type of T.

Code: [Select]

if(index < 0 || index >= _size)
 return false;

Maybe return a default initialized value:

Code: [Select]

if(index < 0 || index >= _size)
 return T();

This now only assumes that T has a default constructor or is a POD.

The same scenario appears in other functions.

[ivanseidel]

Hi,
  Thanks for fast response.  Unfortunately that doesn't work either.  Same errors.   Computers have really been troublesome for me lately. lol.

Sorry for my (fast) but wrong response!

Now I had time to try it out, and seems that you are trying to 'include' the instance of the object, not the pointer to it. Here is how I would do, because then you are still able of passing the object without having to copy it or anything else...

Note that, the type of the LinkedList is not pointer, but the class inside it is. So, if you are adding elements to it, if they are instance objects (not pointers), don't forget the '&' before it...

Perhaps I could work out some examples for the library...

Code: [Select]

#include <LinkedList.h>

LinkedList<int> myLinkedList = LinkedList<int>();
class test
{
public:
  test();
  int x;
};
test::test(){}

LinkedList<test*> myLinkedList2 = LinkedList<test*>();
void setup()
{
  myLinkedList = LinkedList<int>();
  myLinkedList2 = LinkedList<test*>();
}
void loop()
{
}

[ivanseidel]

@ivanseidel, your remove function assumes that bool can be converted to any type of T.

Code: [Select]

if(index < 0 || index >= _size)
 return false;

Maybe return a default initialized value:

Code: [Select]

if(index < 0 || index >= _size)
 return T();

This now only assumes that T has a default constructor or is a POD.

The same scenario appears in other functions.

I think the problem is in fact, storing things larger than a simple pointer to a memory, number, boolean...

returning T(); would only work for object types that are NOT pointers, right?

[pYro_65]

No, default initialization will work on any type that is a POD, primitive, or object that has a default constructor:

Code: [Select]

typedef int* iptr;
iptr i = iptr(); //Works fine.

[Molex1701]

Hi!
Take a look at pointers and objects by instance to understand it better. But in your case you are trying to instantiate a poiinter linked list with an instance.object...

Also, when working with the list within different scope (loop, void, classes...), its a good practice to instantiate as a poiter. (If there will be lots of classes, its a good idea to delete it after you dont need it anymore).

What i use to do is:

Code: [Select]

LinkedList<mytype> *myList;

void setup{
  myList = new LinkedList<mytype>();
}

// In your code
myList->add(....);

Hello,
Thanks for the additional help.  That got me going.  Here is some updated code showing it so that others might get help too:

Code: [Select]


#include <LinkedList.h>

class myNumber
{
public:
  myNumber();
  myNumber(int x);
  int _x;
};
myNumber::myNumber(){}
myNumber::myNumber(int x)
{
  _x=x;
}
//storing a address pointing to Class.
LinkedList<myNumber*> myNumbers = LinkedList<myNumber*>();

void setup()
{
  Serial.begin(9600);
 
  Serial.print("Size ");
  Serial.println(myNumbers.size());
  //make object 
  myNumber object(33);

                //Give list the address to store
  myNumbers.add(&object);
 
 
  Serial.print("Size ");
  Serial.println(myNumbers.size()); //See if list grew
 
  // get returned the address to the object
  // Access members with the -> pointer
  Serial.println(myNumbers.get(0)->_x); // Print out value
}
void loop()
{

}



[khristopheryan]

Hi good day. I tried to use your library to implement my linked list, here's the code that I made:

Code: [Select]

#include <LinkedList.h>

uint8_t buf[16] = {255, 200, 0x03, 0x84, 0x05, 0x06, 0x07, 0x08, 0x00, 0x03, 0x00, 0x00, 0x00, 0x00, 0x20, 0x00};

class IP
{
  public:
    char *name;
};

char *string, *stringA, *temp;
LinkedList<IP *> myList = LinkedList<IP *>();


void setup()
{
  delay(1000);
  Serial.begin(9600);
  string = (char *)malloc(sizeof(char *)*1024);
  stringA = (char *)malloc(sizeof(char *)*1024);
  temp = (char *)malloc(sizeof(char *)*1024);
}

void loop()
{
  int cnt = 0;
  char a[256];
  for(int x = 0; x < sizeof(buf); x++)
  {
    cnt++;
    sprintf(a, "%02X", (uint8_t)buf[x]);
    strcat(stringA, a);
    if(cnt%4 == 0)
    {
      if(strcmp(stringA, "00000000") != 0)
      {
        strcat(string, stringA);
      }
      strcpy(stringA, "");
    }
    buf[x] += 1;
  }
  int len = strlen(string);
  while(len > 0)
  {
    snprintf(temp, 9, "%s", string+len-8);
    strcat(stringA, temp);
    if(len > 8)
    {
      strcat(stringA, "-");
    }
    len -= 8;
  }
  IP *ip = new IP();
  ip->name = stringA;
  myList.add(ip);
  IP *route;
  Serial.print("Size: ");
  Serial.println(myList.size());
  for(int f = 0; f < myList.size(); f++)
  {
    route = myList.get(f);
    Serial.println(route->name);
  }
 
  strcpy(string, "");
  strcpy(stringA, "");
  strcpy(temp, "");
  delay(1000);
}

I'm expecting my output to be:

Code: [Select]

Size: 1
00002000-00030000-05060708-FFC80384
Size: 2
00002000-00030000-05060708-FFC80384
01012101-01040101-06070809-00C90485
Size: 3
00002000-00030000-05060708-FFC80384
01012101-01040101-06070809-00C90485
02022202-02050202-0708090A-01CA0586
Size: 4
00002000-00030000-05060708-FFC80384
01012101-01040101-06070809-00C90485
02022202-02050202-0708090A-01CA0586
03032303-03060303-08090A0B-02CB0687
Size: 5
00002000-00030000-05060708-FFC80384
01012101-01040101-06070809-00C90485
02022202-02050202-0708090A-01CA0586
03032303-03060303-08090A0B-02CB0687
04042404-04070404-090A0B0C-03CC0788
Size: 6
00002000-00030000-05060708-FFC80384
01012101-01040101-06070809-00C90485
02022202-02050202-0708090A-01CA0586
03032303-03060303-08090A0B-02CB0687
04042404-04070404-090A0B0C-03CC0788
05052505-05080505-0A0B0C0D-04CD0889
Size: 7
00002000-00030000-05060708-FFC80384
01012101-01040101-06070809-00C90485
02022202-02050202-0708090A-01CA0586
03032303-03060303-08090A0B-02CB0687
04042404-04070404-090A0B0C-03CC0788
05052505-05080505-0A0B0C0D-04CD0889
06062606-06090606-0B0C0D0E-05CE098A


however, i got

Code: [Select]

Size: 1
00002000-00030000-05060708-FFC80384
Size: 2
01012101-01040101-06070809-00C90485
01012101-01040101-06070809-00C90485
Size: 3
02022202-02050202-0708090A-01CA0586
02022202-02050202-0708090A-01CA0586
02022202-02050202-0708090A-01CA0586
Size: 4
03032303-03060303-08090A0B-02CB0687
03032303-03060303-08090A0B-02CB0687
03032303-03060303-08090A0B-02CB0687
03032303-03060303-08090A0B-02CB0687
Size: 5
04042404-04070404-090A0B0C-03CC0788
04042404-04070404-090A0B0C-03CC0788
04042404-04070404-090A0B0C-03CC0788
04042404-04070404-090A0B0C-03CC0788
04042404-04070404-090A0B0C-03CC0788
Size: 6
05052505-05080505-0A0B0C0D-04CD0889
05052505-05080505-0A0B0C0D-04CD0889
05052505-05080505-0A0B0C0D-04CD0889
05052505-05080505-0A0B0C0D-04CD0889
05052505-05080505-0A0B0C0D-04CD0889
05052505-05080505-0A0B0C0D-04CD0889
Size: 7
06062606-06090606-0B0C0D0E-05CE098A
06062606-06090606-0B0C0D0E-05CE098A
06062606-06090606-0B0C0D0E-05CE098A
06062606-06090606-0B0C0D0E-05CE098A
06062606-06090606-0B0C0D0E-05CE098A
06062606-06090606-0B0C0D0E-05CE098A
06062606-06090606-0B0C0D0E-05CE098A


I'm wondering what could be the problem.

Thanks.