[Published on GitHub] LinkedList Class (Fully implemented)

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))

fun structure to implement!

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))

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

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.

 #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()
{
}
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 *myLinkedList = LinkedList(); then I just get a message about converting.

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:

LinkedList<mytype> *myList;

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

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

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

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.

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

Maybe return a default initialized value:

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.

Molex1701:
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...

#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()
{
}

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

if(index < 0 || index >= _size)

return false;




Maybe return a default initialized value:


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?

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

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

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:

LinkedList<mytype> *myList;

void setup{
  myList = new LinkedList();
}

// 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:

#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()
{
 
}

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

#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:

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

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.

quick guess(not dived into the code details)

  • not allocating the stringA? and therefore reusing the same buffer over and over again?
  string = (char *)malloc(sizeof(char *)*1024);
  stringA = (char *)malloc(sizeof(char *)*1024);
  temp = (char *)malloc(sizeof(char *)*1024);

Which Arduino are you expecting to be able to allocate 3072 bytes of SRAM on? Not a 328-based Arduino with 2048 bytes of SRAM.

I'm using the arduino mega 2560.

quick guess(not dived into the code details)

  • not allocating the stringA? and therefore reusing the same buffer over and over again?

I don't think that is the problem because all the nodes in the linked list are changed with the value of the new node inserted. If it's using the same buffer over and over again, isn't it that the value of all the nodes will be the value of the first node stored in the list?

PaulS:

  string = (char *)malloc(sizeof(char *)*1024);

stringA = (char *)malloc(sizeof(char *)*1024);
  temp = (char *)malloc(sizeof(char *)*1024);



Which Arduino are you expecting to be able to allocate 3072 bytes of SRAM on? Not a 328-based Arduino with 2048 bytes of SRAM.

I didn't notice it at first either, but the allocations above actually reserve 6144 bytes. (sizeof( char* ) == 2).

Hmmm. I missed that, too. It also means that the cast up front should be (char **), not (char *). That means that the variable type is wrong, too.

I think that you should be allocating memory for the string everytime you create a new one, otherwise you will just be overriding it, and all values in the IP struct inside the LinkedList, will ref. the same pointer.

And also, alocating more than the arduino can, can cause it to crash :astonished:

If that doesn't work, I can try it here (without arduino right now...)

Thank you ivanseidel for making this code public domain.

Yeah! Someone who actually gets that you cannot use GPL and LGPL embedded code in a commercial project!

I found other list like libraries that are licensed either GPL or LGPL. Basically they are useless to me because of my application. For something at home they would be fine, but for anything else they are useless.

I write open source code and have released a few projects mostly for hobbies. I always release under MIT for this reason. If I am giving code away I want people to use it! The only reason I do MIT is for CYA.

Again, thank you! You saved me having to write my own list.