Pages: [1] 2   Go Down
Author Topic: [Published on GitHub] LinkedList Class (Fully implemented)  (Read 3483 times)
0 Members and 1 Guest are viewing this topic.
Brasil
Offline Offline
Full Member
***
Karma: 4
Posts: 124
View Profile
WWW
 Bigger Bigger  Smaller Smaller  Reset Reset

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
« Last Edit: July 20, 2013, 08:10:15 pm by ivanseidel » Logged


Global Moderator
Netherlands
Offline Offline
Shannon Member
*****
Karma: 170
Posts: 12487
In theory there is no difference between theory and practice, however in practice there are many...
View Profile
 Bigger Bigger  Smaller Smaller  Reset Reset

Thanks for sharing,
Logged

Rob Tillaart

Nederlandse sectie - http://arduino.cc/forum/index.php/board,77.0.html -
(Please do not PM for private consultancy)

Brasil
Offline Offline
Full Member
***
Karma: 4
Posts: 124
View Profile
WWW
 Bigger Bigger  Smaller Smaller  Reset Reset

I'm happy to help...
Logged


Brasil
Offline Offline
Full Member
***
Karma: 4
Posts: 124
View Profile
WWW
 Bigger Bigger  Smaller Smaller  Reset Reset

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


Global Moderator
Netherlands
Offline Offline
Shannon Member
*****
Karma: 170
Posts: 12487
In theory there is no difference between theory and practice, however in practice there are many...
View Profile
 Bigger Bigger  Smaller Smaller  Reset Reset

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!
Logged

Rob Tillaart

Nederlandse sectie - http://arduino.cc/forum/index.php/board,77.0.html -
(Please do not PM for private consultancy)

Brasil
Offline Offline
Full Member
***
Karma: 4
Posts: 124
View Profile
WWW
 Bigger Bigger  Smaller Smaller  Reset Reset

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
Logged


Offline Offline
Newbie
*
Karma: 0
Posts: 3
View Profile
 Bigger Bigger  Smaller Smaller  Reset Reset

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

Brasil
Offline Offline
Full Member
***
Karma: 4
Posts: 124
View Profile
WWW
 Bigger Bigger  Smaller Smaller  Reset Reset

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:
LinkedList<mytype> *myList;

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

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


Offline Offline
Newbie
*
Karma: 0
Posts: 3
View Profile
 Bigger Bigger  Smaller Smaller  Reset Reset

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

North Queensland, Australia
Offline Offline
Edison Member
*
Karma: 53
Posts: 1804
View Profile
WWW
 Bigger Bigger  Smaller Smaller  Reset Reset

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:
if(index < 0 || index >= _size)
  return false;

Maybe return a default initialized value:
Code:
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.
« Last Edit: February 05, 2014, 12:01:49 am by pYro_65 » Logged


Brasil
Offline Offline
Full Member
***
Karma: 4
Posts: 124
View Profile
WWW
 Bigger Bigger  Smaller Smaller  Reset Reset

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


Brasil
Offline Offline
Full Member
***
Karma: 4
Posts: 124
View Profile
WWW
 Bigger Bigger  Smaller Smaller  Reset Reset

@ivanseidel, your remove function assumes that bool can be converted to any type of T.
Code:
if(index < 0 || index >= _size)
  return false;

Maybe return a default initialized value:
Code:
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?
Logged


North Queensland, Australia
Offline Offline
Edison Member
*
Karma: 53
Posts: 1804
View Profile
WWW
 Bigger Bigger  Smaller Smaller  Reset Reset

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

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


Offline Offline
Newbie
*
Karma: 0
Posts: 3
View Profile
 Bigger Bigger  Smaller Smaller  Reset Reset

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

Logged

Offline Offline
Newbie
*
Karma: 0
Posts: 3
View Profile
 Bigger Bigger  Smaller Smaller  Reset Reset

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

Code:
#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:
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:
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.
Logged

Pages: [1] 2   Go Up
Jump to: