[Published on GitHub] LinkedList Class (Fully implemented)

ivansg · July 21, 2013, 12:58am

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::LinkedList() - Constructor.
LinkedList::~LinkedList() - Destructor. Clear Nodes to minimize memory.
int LinkedList::size() - Returns the current size of the list.
bool LinkedList::add(T) - Add element T at the END of the list.
bool LinkedList::add(int index, T) - Add element T at index of the list.
bool LinkedList::unshift(T) - Add element T at the BEGINNING of the list.
bool LinkedList::set(int index, T) - Set the element at index to T.
T LinkedList::remove(int index) - Remove element at index. Return the removed element.
T LinkedList::pop() - Remove the LAST element. Return the removed element.
T LinkedList::shift() - Remove the FIRST element. Return the removed element.
T LinkedList::get(int index) - Return the element at index.
void LinkedList::clear() - Removes all elements.

For more information, and Latest releases go to GitHub - ivanseidel/LinkedList: 🔗 A fully implemented LinkedList made to work with general Microcontrollers and Arduino projects

Fell free to commit new changes and use it.

Ivan

robtillaart · July 21, 2013, 12:04pm

Thanks for sharing,

ivansg · August 22, 2013, 12:28am

I'm happy to help...

ivansg · September 4, 2013, 9:42pm

-------- 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 · September 11, 2013, 5:32pm

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

Lecture 12: Skip Lists | Introduction to Algorithms (SMA 5503) | Electrical Engineering and Computer Science | MIT OpenCourseWare -

fun structure to implement!

ivansg · September 11, 2013, 7:55pm

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

system · February 4, 2014, 4:32am

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.

ivansg · February 4, 2014, 9:16am

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(....);

system · February 5, 2014, 2:32am

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

pYro_65 · February 5, 2014, 4:39am

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.

ivansg · February 5, 2014, 8:07am

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

ivansg · February 5, 2014, 8:10am

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?

pYro_65 · February 5, 2014, 10:08am

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.

system · February 6, 2014, 12:20am

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

system · February 21, 2014, 8:06am

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.

robtillaart · February 21, 2014, 6:32pm

quick guess(not dived into the code details)

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

system · February 21, 2014, 6:44pm

  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.

system · February 22, 2014, 2:58am

I'm using the arduino mega 2560.

system · February 22, 2014, 3:03am

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?

pYro_65 · February 22, 2014, 5:54am

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

Topic		Replies	Views
[Published on GitHub] LinkedList Class (Fully implemented) Arduino Due	1	1014	May 6, 2021
linked list advice needed Programming Questions	9	3587	May 5, 2021
Compilation problems for my linked list library Programming Questions	4	1711	May 5, 2021
Creating functional get and set methods. Programming Questions	9	1596	May 5, 2021
LinkedList giving unexpected output Programming Questions	2	417	May 5, 2021

[Published on GitHub] LinkedList Class (Fully implemented)

Related Topics