Scripting Helpers is winding down operations and is now read-only. More info→
Ad
Log in to vote
7

What is Intrusive linked list or just Linked List?

Asked by
Zafirua 1348 Badge of Merit Moderation Voter
5 years ago
Edited 5 years ago

I was looking at the The Basics of Optimization referenced by Avigant. While I was reading through it, I found couple things to be interesting.

Stravant and BlueTaslem mentioned something about Intrusive Linked Lists. From the text alone, I immediately assumed some things.

  • It is a form of tables.
  • It is somewhat different from regular tables?

I googled it without specifying Lua and saw its common usage in C and C++. Here is the code of Intrusive Data Structure I saw. I have almost no knowledge on C language but this was the first information I found.

typedef struct intrusiveListNode {
struct intrusiveListNode *next;
struct intrusiveListNode *prev;
} IntrusiveListNode;

typedef is a C feature which creates a new name for an existing data type.

struct is basically a table.

IntrusiveListNode in the end is just a way to end the syntax?

Now, from my views, the actually object in the table never exists because it is telling that the intrusiveListNode to either go previous or next? I will leave this to here and move on to what Lua has to say about this.

Lua also had a similar approach and implemented a loop into the table

list = {next = list; value = "Zafirua"};

local l = list;

while l do
   print(l.value);
   l = l.next;
end;

It prints Zafirua

I fail to understand this code. This is my understanding so far. Mind you, it is garbage.

  • A Table named list is created.
  • next is the identifier that is getting the objects from the list. It's job is to return the next object in the list.
  • value is the object that is inside the list.
  • l is now going to gain all the list's objects.
  • Implemented a loop
  • prints value; hence prints Zafirua
  • Since there are no more objects in the list, the loop will stop there.

Assuming from my that knowledge, I went on testing more stuff and failed miserably on this part.

list = {next = list; a = "Zafirua"; b = "Mini-Zafirua"; c = "-Zafirua" };

local l = list;

while l do
    print(l.a);
    l = l.next;
    print(l.b);
end;

The typical attempt to index nil value

I do not understand this. I am pretty sure my understanding is wrong in this. Can someone correct me and explain what my error is? Also an explanation on how this might be useful would be greatly appreciated as

References if you want to check them out

0
How did the links suddenly break? It was working a moment ago.....Fixed it now.  Zafirua 1348 — 5y
0
I think what is happening is that when we say l = l.next, we are doing l = {l = {value},value} saSlol2436 716 — 5y
0
The wiki has more information http://wiki.roblox.com/index.php?title=Linked_list saSlol2436 716 — 5y
0
^ Thanks for the link. Zafirua 1348 — 5y
View all comments (2 more)
0
your welcome saSlol2436 716 — 5y
0
By the way, I have a similar question about optimization, memoized functions. saSlol2436 716 — 5y

1 answer

Log in to vote
10
Answered by
BlueTaslem 18071 Moderation Voter Administrator Community Moderator Super Administrator
5 years ago

The topic is ways to store sequences of values! A "sequence" means that you have many things, and you care about the order of things: you have a first thing, a second thing, a third thing, etc.

Arrays

An array is a way to store a sequence of values in order so that all of the values are "next to" each other.

If collection is an array, the elements are

  • collection[1]
  • collection[2]
  • collection[3]
  • etc

All the values are "next to" each other inside collection.

Lua arrays are simple to make. An array of the first three Greek letters is

alphabetArray = {"alpha", "beta", "gamma"}

This is "shorthand" for the more explicit

alphabetArray = {
    [1] = "alpha",
    [2] = "beta",
    [3] = "gamma",
}

print(alphabetArray[1]) --> alpha
print(alphabetArray[2]) --> beta
print(alphabetArray[3]) --> gamma

ie, you just put the ith element at index [i].

In Lua, you can find out how many elements are in array by using the # operator: #collection is 0 for an empty array, 15 for an array that has values at entries [1], [2], ..., [15], etc.

Linked Lists

A linked list is a way to store a sequence of values in a bunch of different places; each value points to the next value.

If collection is a linked list, the elements could be

  • collection.first
  • collection.rest.first
  • collection.rest.rest.first
  • collection.rest.rest.rest.first
  • collection.rest.rest.rest.rest.first
  • etc

Unlike an array, you cannot immediately know how many elements a linked list has or what value is at any position other than the first! That's because you have to follow .rests n-1 times to get to the nth value.

However, you can represent an empty linked list as false or nil. A linked list with at least one value is a table with a .head, the first value, and a .rest a linked list of the rest of the data.

A linked list of the first three Greek letters is

alphabetLinkedList = {
    first = "alpha",
    rest = {
        first = "beta",
        rest = {
            first = "gamma",
            rest = nil,
        },
    },
}

This is a bit wordy! A function that sticks one element in front of a list is traditionally called cons:

function cons(first, rest)
    return {
        first = first,
        rest = rest,
    }
end

alphabetLinkedList = cons("alpha", cons("beta", cons("gamma", nil)))

print(alphabetLinkedList.first) --> alpha
print(alphabetLinkedList.rest.first) --> beta
print(alphabetLinkedList.rest.rest.first) --> gamma

Linked lists are typically operated on recursively. For example, here is a recursive function that tells you how long a linked list is:

function length(list)
    if not list then
        -- nil is a length-0 linked list
        return 0
    end

    -- This list is one element, then `rest`.
    -- So the length of `list` is one more than the length of `list.rest`
    return 1 + length(list.rest)
end

print(length(alphabetLinkedList)) --> 3

Here's one that lets you get the ith thing from a linked list:

function get(list, i)
    if i == 1 then
        -- We're looking for the first thing!
        assert(list, "list must not be empty")
        return list.first
    end

    -- The ith thing in this list is (i-1)th in the rest
    -- because we are moving past the first element
    return get(list.rest, i - 1)
end

print(get(alphabetLinkedList, 1)) --> alpha
print(get(alphabetLinkedList, 2)) --> beta
print(get(alphabetLinkedList, 3)) --> gamma

Intrusive Linked List

The difference between an "intrusive" data structure and a "non-intrusive" data structure is not important in dynamic languages like Lua.

First, an intrusive data-structure only makes sense when your values are tables (the simple string example above won't work).

For a linked list, it just means getting rid of the .first field -- a (non-empty) list simply has all of the fields you're interested in!

For example, consider this array-of-letter-informations:

local array = {
    {name = "alpha", letter = "a"},
    {name = "beta", letter = "b"},
    {name = "gamma", letter = "c"},
}

As a non-intrusive linked list, it could look like this:

alphabetLinkedList = {
    first = {name = "alpha", letter = "a"},
    rest = {
        first = {name = "beta", letter = "b"},
        rest = {
            first = {name = "gamma", letter = "c"},
            rest = nil,
        },
    },
}

As an intrusive linked list, it would look like this;

alphabetLinkedList = {
    -- data from `first`
    name = "alpha",
    letter = "a",

    -- rest of list
    rest = {
        -- data from `first`
        name = "beta",
        letter = "b",

        -- rest of list
        rest = {
            -- data from `first`
            name = "gamma",
            letter = "c",

            -- rest of list
            rest = nil,
        },
    },
}

The only thing I did was "flatten" the first field into the list.

In Lua, you're probably going to use intrusive linked lists more often -- you create them by just setting .rest or .next to the next thing in the list!

In languages like C++ or Java, intrusive lists are much less common.

Ad

Answer this question