Fun with Linked Lists

[ned]

I have a project in which I'm trying to use a linked list. An array is an acceptable alternative, but it seems like a good opportunity to learn about recursive data structures. I've used linked lists in C, which might be hurting my ability to use them in LabVIEW since I'm accustomed to thinking in pointers. Is there a neat way I can maintain a reference to the head of a list while continually adding items to the tail? Aristos Queue posted an implementation that allows an insert at any point but traverses the list recursively in order to do it, which seems inefficient.

I'd like to maintain the current location in a shift register, with a function in the loop that takes the current index, adds a new element on the end, and returns the new element so it can be put in the shift register. I can't find a way to do that and maintain the list order. Either I keep adding to the beginning of the list, and the elements are in reverse order, or I lose track of the beginning of the list. The best solution I've found so far is to maintain both the previous and next element in the list (a doubly linked list), insert them backwards, and then reverse the list after adding all elements to it. Is there another way?

[Yair]

I'm not sure I understand the problem you're running into (I haven't tried this myself), but DVRs (a new feature of 2009) can probably simplify the implementation a lot, because they're pretty much the nearest thing you have to a pointer and making a copy of the reference is cheap. You would still need to traverse the list (iteratively, not recursively, which I assume is what AQ's example does as well, although it's been a while since I've seen the code) to get to where you want, but that's a basic part of the design.

This feature won't help you if you're trying to create a cyclic graph, because to access the data a second time, the first lock must be released.

[ShaunR]

An array is a poor replacement for a linked list. A linked list is atomic and not contiguous in memory (hence the next-node pointer refs) and therefore doesn't suffer from memory re-allocation penalties when inserting, deleting or appending. You simply allocate the node and update the appropriate next-node pointer values. (The downside to this is of course fragmented memory). The main advantage of linked lists is that the operation time for insertion, append and deletion is consistent, which is not the case when array re-allocation occurs, since the re-allocation time is variable dependent on the array size.

You can think of an array as a special (limited) case of a linked list where the list is of a fixed length and the pointer is the previous-node pointer+1. This case will perform the same as a linked list, but as soon as you insert, delete or append past the array length you will again get re-allocation penalties.

I avoid linked lists like the plague in LV since I haven't come accross an effecient way of implementing them because the whole point of labview is that you don't have to worry about pointers . Perhaps a better way might be to write a dll (API) that manipulates your list. This may yield better results although you have other overheads but at least they will be consistent.

Of course. this is only applicable if performance is the attractive quality of your linked list. If performance isn't an issue then just use a standard array and use the standard LV prototypes to insert, delete and append.

[MikaelH]

The best solution I've found so far is to maintain both the previous and next element in the list (a doubly linked list), insert them backwards, and then reverse the list after adding all elements to it. Is there another way?

Hi Shaun

It looks like your after the “Iterator” design pattern.

(Page 257, in Design Patterns http://www.amazon.com/Design-Patterns-Elements-Reusable-Object-Oriented/dp/0201633612).

Just google it.

E.g. http://www.cs.unb.ca/profs/wdu/cs4015w02/ch5d.htm

Cheers,

Mikael

[ned]

Thanks for all the comments, but I should have phrased my original question more clearly. I'm trying to learn about what can be done with recursive data structures (using a parent class as a member of a child class), without using any type of reference (DVR, queue). I'm looking for an implementation, if anyone has one, that can efficiently add items to the end of a list (without having to iterate through the entire list for each insert). The problem is that, as far as I can tell, it's not possible to keep track of both the beginning and end of the list at the same time. Adding an item to the end of the list invalidates the front, because the front can only point at the list at a specific point in time. In C I would use two pointers, one to the beginning of the list and one for the current end, and I can't see a way to duplicate that structure in LabVIEW.

[ShaunR]

Hi Shaun

It looks like your after the “Iterator” design pattern.

(Page 257, in Design Patterns http://www.amazon.co...d/dp/0201633612).

Just google it.

E.g. http://www.cs.unb.ca...015w02/ch5d.htm

Cheers,

Mikael

I'm not after anything, except a pay rise.lol

[ShaunR]

Thanks for all the comments, but I should have phrased my original question more clearly. I'm trying to learn about what can be done with recursive data structures (using a parent class as a member of a child class), without using any type of reference (DVR, queue). I'm looking for an implementation, if anyone has one, that can efficiently add items to the end of a list (without having to iterate through the entire list for each insert). The problem is that, as far as I can tell, it's not possible to keep track of both the beginning and end of the list at the same time. Adding an item to the end of the list invalidates the front, because the front can only point at the list at a specific point in time. In C I would use two pointers, one to the beginning of the list and one for the current end, and I can't see a way to duplicate that structure in LabVIEW.

I'm probably missing something huge here. But the beginning of an array is index(0) and the end is index(length-1). This is true if you add, delete or insert. The next item in the list is current index+1 and you just maintain an index to the current place in the list/array. No iteration, uses LV primitives but suffers from re-allocation penalties.

[ned]

I'm probably missing something huge here. But the beginning of an array is index(0) and the end is index(length-1). This is true if you add, delete or insert. The next item in the list is current index+1 and you just maintain an index to the current place in the list/array. No iteration, uses LV primitives but suffers from re-allocation penalties.

No, you're not missing anything here - an array is an easy way to do this in LV. I'm just curious if the new features in LV allow it to be done neatly as a linked list, since that's how I'd do it in C. I'm building a list of chemical reactions. The list is read from a file, so I don't know in advance how large the list will need to be. Then I need to run those reactions. Sometimes the user might want to re-run a reaction before proceeding, but I'll never need to back up to a previous reaction, so a linked list is a reasonable structure. From a performance point of view there's no problem with either implementation, since the list is short and I only need to build it once when the run starts. My question is pure curiousity as to whether a LabVIEW implementation exists (or can exist) that does what I want.

[Yair]

I'm trying to learn about what can be done with recursive data structures ... without using any type of reference (DVR, queue).

...

In C I would use two pointers.

And you don't see any problem with these two statements? A linked list has pointers as part of the mechanism. AQ posted code which allows you to swap two pieces of data without using references, but that would only work with two pieces and would only guarantee no copies if you do it exactly right.

You should note that the problem is not with a recusive data structure in itself. The problem is that you want not just the data type to be recursive, but the data itself to be recursive as well, which is kind of a problem in the data flow world of LabVIEW.

[ShaunR]

No, you're not missing anything here - an array is an easy way to do this in LV. I'm just curious if the new features in LV allow it to be done neatly as a linked list, since that's how I'd do it in C. I'm building a list of chemical reactions. The list is read from a file, so I don't know in advance how large the list will need to be. Then I need to run those reactions. Sometimes the user might want to re-run a reaction before proceeding, but I'll never need to back up to a previous reaction, so a linked list is a reasonable structure. From a performance point of view there's no problem with either implementation, since the list is short and I only need to build it once when the run starts. My question is pure curiousity as to whether a LabVIEW implementation exists (or can exist) that does what I want.

Yes. There is a very easy way to do what you want. But not in the way you want to do it. Your array would be short right? (By short I'm thinking less than 2000 lines!)

Just load all lines of the file using the "ReadLinesFromFile.vi" (-1 as the lines argument will read all lines regardless of file size) or "ReadFromSpreadsheetFile.vi" (the output of this vi is already an array type and also reads all lines regardless of size) to an array and let the user index through it. If you give him a back button (decrement) then he will also be able to go backwards (never say never...users are illogical creatures) with little effort on your part.

Labview does this sort of thing much better than C/C++ since you don't have to declare array sizes before you start and arrays are self re-allocating so you don't have to manage the re-allocation (as you would have to in C). You also don't have to worry about overrunning the end of the array. GPFs are rare in LV

Should take you 2 mins (including waiting for LV to load )

KISS!

[ned]

I already wrote the array implementation - that's where I started, and it worked. As a weekend problem I was investigating other ways to do it. Here's a simplified, stripped down version of my linked list; is there a better way to do this, while still using a recursive data structure?

By the way, I discovered in the process that the following code crashes LabVIEW, almost immediately and with no error message at all:

Linked List.zip