MATLAB linked list

Question

What are some possible ways to implement a linked list in MATLAB?

Note: I am asking this question for pedagogical value, not practical value. I realize that if you're actually rolling your own linked list in MATLAB, you're probably doing something wrong. However, I'm a TA for a class that is MATLAB-intensive this semester, and my goal in asking this question is to understand the general structure of the language better. As MATLAB's general purpose programming facilities are a bit unusual, I feel a question like this will help me understand them.

Solution 1

MATLAB has access to Java:

>> a=java.util.LinkedList;
>> li=a.listIterator;
>> li.add(2);
>> li.add(int8(77));
>> li.add(77);
>> li.add(boolean(true));
>> li.add('Mr. Bill');
>> li.previous();
>> li.add([1 2 3 4 5]);
>> a

a =

[2.0, 77, 77.0, true, [D@66a917, Mr. Bill]

>> a.get(4)

ans =

     1
     2
     3
     4
     5

The one downside of this approach is because MATLAB doesn't have a way to marshal or serialize arbitrary MATLAB objects into Java, you're limited to floating point numbers, integers (need to cast them in MATLAB using int8 etc.), booleans, strings, arrays, and Java objects.

Solution 2

The link Lulu suggested in the comments is probably the choice I would make if I were wanting to implement a linked list in MATLAB. However, this approach would stray off into the object-oriented features of MATLAB, which may not be what you want since you mention wanting "to understand the general structure of the language better." As such, you may do better with a simpler example that incorporates general core features of MATLAB programming.

A number of general features have been mentioned in other answers, such as matrices and matrix indexing, creating structures, and using nested functions and function handles. I'll go through an example that makes use of all these features and hopefully gives a nice introduction to a number of key concepts in MATLAB...

Sample code:

Save the code below in a file called linked_list.m on the MATLAB path:

function listObject = linked_list(values)

  data = reshape(values,1,[]);
  listObject = struct('display',@display_list,...
                      'addAfter',@add_element,...
                      'delete',@delete_element);

  function display_list
    %# Displays the data in the list
    disp(data);
  end

  function add_element(values,index)
    %# Adds a set of data values after an index in the list, or at the end
    %#   of the list if the index is larger than the number of list elements
    index = min(index,numel(data));
    data = [data(1:index) reshape(values,1,[]) data(index+1:end)];
  end

  function delete_element(index)
    %# Deletes an element at an index in the list
    data(index) = [];
  end

end

Description:

The function linked_list accepts an arbitrary-sized matrix and first reshapes it into a row vector using the RESHAPE function. This becomes the initial "linked list", stored in the variable data.

Next, a structure is created (using the STRUCT function) which has three elements: display, addAfter, and delete. Each of these fields stores a function handle to one of three functions that is nested within the parent function linked_list. These nested functions are able to access the variable data stored in the parent function.

The listObject structure is returned from linked_list. As long as this structure exists in the workspace, and thus as long as the function handles it contains exist, then the data variable will persist even after the function linked_list returns. We can then invoke the nested functions (using their handles) to modify the variable data. Here's an example...

First, create a linked list "object" and display the contents:

>> listObj = linked_list([1 2 3]);  %# A linked list with three elements
>> listObj.display()  %# Access the `display` field and invoke the function
     1     2     3

Next, add an element "4" after the second list element and display:

>> listObj.addAfter(4,2)  %# Access the `addAfter` field and invoke the function
>> listObj.display()
     1     2     4     3

And finally, delete the second list element and display:

>> listObj.delete(2)  %# Access the `delete` field and invoke the function
>> listObj.display()
     1     4     3

Note how the nested functions add_element and delete_element use matrix indexing to modify the variable data.

You can extend this example to create numerous other nested functions for operating on a linked list, adding new fields to the structure to store their function handles.

Solution 3

Creating a linked list in MATLAB isn't actually too bad with the new object oriented structure. I think what most people miss is that most pointer behavior can be achieved in MATLAB through the use of "handle classes".

So, start with a Node class...

classdef Node < handle

       properties
           next
           prev
           value
       end

       methods
            function this = Node(inVal)
                this.value = inVal;
            end
       end
 end 

Then your linked list class would look something like this...

classdef LinkedList < handle

           properties
               firstNode
               lastNode
           end

           methods
               function this = LinkedList(newNode)
                   % Initialize LinkedList with newNode
                   this.firstNode = newNode;
                   this.lastNode = newNode;
               end
               function addNode(this,newNode)
                   % Add newNode to the end of the list
                   newNode.prev = this.lastNode;
                   this.lastNode.next = newNode;
                   this.lastNode = newNode;
               end
           end
    end

I threw this together pretty quickly so I don't know if this will work as written. But if you're just interested in what the structure of a MATLAB linked list would look like, I'm sure this is enough to get you started.

The key concept here is the handle superclass. Whenever you create a class of type handle, you get a "pointer" to that class. That pointer can be passed to other functions or classes thus making it possible to have the nodes of the list point to other nodes.

You can find out more about this here.

Solution 4

You can implement a linked list with a function handle to a nested function which keeps the linked list data in the nested parent's workspace.

--Loren

Solution 5

I don't think you (or I) can do dynamic data structures 'in' MATLAB. We have to use MATLAB OO features and MATLAB classes. Since I think that these facilities are really a MATLAB wrapper around Java I make the bold claim that those facilities are outside MATLAB. A matter of semantics, I concede. If you want to do dynamic data structures with MATLAB, you have to use OO and classes, you can't do it with what I think of as the core language, which lacks pointers at the user level.

View more solutions