Matlab Implementing Linked Lists

Displaying Fully Commented Example Code

Open class code in a popup window — Use this link if you want to see the code for this class annotated with links to descriptive sections.

Open class definition file in the MATLAB editor. — Use this link if you want to save and modify your version of the class.

To use the class, create a folder named @dlnode and save dlnode.m to this folder. The parent folder of @dlnode must be on the MATLAB path. Alternatively, save dlnode.m to a path folder.

Important Concepts Demonstrated

This section discusses concepts that are important in object-oriented design, and which are illustrated in this example.

Encapsulation

This example shows how classes encapsulate the internal structure used to implement the class design (a doubly linked lists). Encapsulation conceals the internal workings of the class from other code and provides a stable interface to programs that use this class. It also prevents client code from misusing the class because only class methods can access certain class data.

Class methods define the operations that you can perform on nodes of this class. These methods hide the potentially confusing process of inserting and removing nodes, while at the same time providing an interface that performs operations simply:

Creating a node by passing the constructor a data value
Inserting nodes with respect to other nodes in the list (before or after)
Removing nodes from the list

See Defining the dlnode Class for the implementation details.

Handle Class Behavior

This example shows an application of a handle class and explains why this is the best choice for the class. See Why a Handle Class for Doubly Linked Lists?.

dlnode Class Design

This example defines a class for creating the nodes of doubly linked lists in which each node contains:

Data array
Link to the next node
Link to the previous node

Each node has methods that enables the node to be:

Disconnected from a linked list
Connected before a specified node in a linked list
Connected after a specific node in a linked list

Class Properties

The dlnode class implements each node as a handle object with three properties:

Data — Contains the data for this node
Next — Contains the handle of the next node in the list (SetAccess = private)
Prev — Contains the handle of the previous node in the list (SetAccess = private)

This diagram shows a three-node list n1, n2, and n3. It also shows how the nodes reference the next and previous nodes.

Class Methods

The dlnode class implements the following methods:

dlnode — Constructs a node and assigns the value passed as input to the Data property
insertAfter — Inserts this node after the specified node
insertBefore — Inserts this node before the specified node
disconnect — Removes this node from the list
disp — Overloads default disp function so that the Data property displays on the command line for scalar objects and the dimension of the array displays for object arrays
delete — Removes this node from the list before it is destroyed

Creating Doubly Linked Lists

You create a node by passing the node’s data to the dlnode class constructor. For example, these statements create three nodes with sequential integer data just for simplicity:

n1=dlnode(1);
n2=dlnode(2);
n3=dlnode(3);

You build these nodes into a doubly linked list using the class methods:

n2.insertAfter(n1)
n3.insertAfter(n2)

Now the three nodes are linked. The dlnode disp method returns the data for the node referred to:

Why a Handle Class for Doubly Linked Lists?

n1.Next % Points to n2
ans =
Doubly-linked list node with data:
     2
n2.Next.Prev % Points back to n2
ans =
Doubly-linked list node with data:
     2 
n1.Next.Next % Points to n3
ans =
Doubly-linked list node with data:
     3 
n3.Prev.Prev % Points to n1
ans =
Doubly-linked list node with data:
     1

Each node is unique in that no two nodes can be previous to or next to the same node. Suppose a node object, node, contains in its Next property the handle of the next node object, node.Next. Similarly, the Prev property contains the handle of the previous node, node.Prev. Using the three-node linked list defined in the previous section, you can demonstrate that the following statements are true:

n1.Next == n2
n2.Prev == n1

Now suppose you assign n2 to x:

x = n2;

The following two equalities are then true:

x == n1.Next
x.Prev == n1

But each instance of a node is unique so there is only one node in the list that can satisfy the conditions of being equal to n1.Next and having a Prev property that contains a handle to n1. Therefore, x must point to the same node as n2.

This means there has to be a way for multiple variables to refer to the same object. The MATLAB handle class provides a means for both x and n2 to refer to the same node. All instances of the handle class are handles that exhibit the copy behavior described previously.

Notice that the handle class defines the eq method (use methods(‘handle’) to list the handle class methods), which enables the use of the == operator with all handle objects.

[important]See Comparing Handle and Value Classes for more information on kinds of MATLAB classes.[/important]

[important]See The Handle Superclass for more information about the handle class.[/important]

Defining the dlnode Class

The following examples use this doubly linked list (see Displaying Fully Commented Example Code before using this class):

n1 = dlnode(1);
n2 = dlnode(2);
n3 = dlnode(3);
n2.insertAfter(n1)
n3.insertAfter(n2)

Class Properties

The dlnode class is itself a handle class because it is derived from the handle class. Note that only class methods can set the Next and Prev properties (SetAccess = private). Using private set access prevents client code from performing any incorrect operation with these properties. The dlnode class defines methods that perform all the operations that are allowed on these nodes. Here are the property definition blocks:

classdef dlnode < handle
   properties
      Data
   end 
   properties (SetAccess = private)
      Next
      Prev
   end

Creating a Node Object

To create a node object, you need to specify only the node's data.

function node = dlnode(Data)
   if nargin > 0
      node.Data = Data;
   end
end

Disconnecting Nodes

When you add the node to a list, the class methods that perform the insertion set the Next and Prev properties. See Inserting Nodes.

The disconnect method removes a node from a list and repairs the list by reconnecting the appropriate nodes. The insertBefore and insertAfter methods always call disconnect on the node to insert before attempting to connect it to a linked list. This ensures the node is in a known state before assigning it to the Next or Prev property:

function disconnect(node)
   if ~isscalar(node)
      error('Nodes must be scalar')
   end
   prevNode = node.Prev;
   nextNode = node.Next;
   if ~isempty(prevNode)
      prevNode.Next = nextNode;
   end
   if ~isempty(nextNode)
      nextNode.Prev = prevNode;
   end
   node.Next = [];
   node.Prev = [];
end

For example, suppose you remove n2 from the three-node list discussed above (n1–n2–n3):

n2.disconnect;

disconnect removes n2 from the list and repairs the list with the following steps:

n1 = n2.Prev;
n3 = n2.Next;
if n1 exists, then
   n1.Next = n3;
if n3 exists, then
   n3.Prev = n1

Now the list is rejoined because n1 connects to n3 and n3 connects to n1. The final step is to ensure that n2.Next and n2.Prev are both empty (i.e., n2 is not connected):

% These properties have private SetAccess
% so they can be set only within class methods
n2.Next = [];
n2.Prev = [];

Inserting Nodes

There are two methods for inserting nodes into the list—insertAfter and insertBefore. These methods perform similar operations, so this section describes only insertAfter in detail.

methods
   function insertAfter(newNode,nodeBefore)
      disconnect(newNode);
      newNode.Next = nodeBefore.Next;
      newNode.Prev = nodeBefore;
      if ~isempty(nodeBefore.Next)
         nodeBefore.Next.Prev = newNode;
      end
      nodeBefore.Next = newNode;
   end

How insertAfter Works: First insertAfter calls the disconnect method to ensure that the new node is not connected to any other nodes. Then, it assigns the newNode Next and Prev properties to the handles of the nodes that are after and before the newNode location in the list.

For example, suppose you want to insert a new node, nnew, after an existing node, n1, in a list containing n1—n2.

First, create nnew:

nnew = dlnode(rand(3));

Next, call insertAfter to insert nnew into the list after n1:

nnew.insertAfter(n1)

The insertAfter method performs the following steps to insert nnew in the list between n1 and n2:

% n1.Next is currently n2, set nnew.Next to n1.Next (which is n2)
   nnew.Next = n1.Next; 
% nnew.Prev must be set to n1
   nnew.Prev = n1;
% if n1.Next is not empty, then
% n1.Next is still n2, so n1.Next.Prev is n2.Prev, which is set to nnew
   n1.Next.Prev = nnew; 
% n1.Next is now set to nnew
   n1.Next = nnew;

Displaying a Node on the Command Line

All objects call a default disp function, which displays information about the object on the command line (unless display is suppressed with a semicolon). The default disp function is not useful in this case because the Next and Prev properties contain other node objects. Therefore, the dlnode class overloads the default disp function by implementing its own disp class method. This disp method displays only a text message and the value of the Data property, when used with scalar objects, and array dimensions when used with object arrays.

function disp(node)
% DISP  Display a link node
   if (isscalar(node))
      disp('Doubly-linked list node with data:')
      disp(node.Data)
   else 
      % If node is an object array, display dimensions
      dims = size(node);
      ndims = length(dims);
      % Counting down in for loop avoids need to preallocate dimcell
      for k = ndims-1:-1:1
         dimcell{k} = [num2str(dims(k)) 'x'];
      end
      dimstr = [dimcell{:} num2str(dims(ndims))];
      disp([dimstr ' array of doubly-linked list nodes']);
   end
end

Deleting a Node Object

MATLAB destroys a handle object when you reassign or delete its variable or when there are no longer any references to the object (see Handle Class Delete Methods for more information). When you define a delete method for a handle class, MATLAB calls this method before destroying the object.

The dlnode class defines a delete method because each dlnode object is a node in a doubly linked list. If a node object is going to be destroyed, the delete method must disconnect the node and repair the list before allowing MATLAB to destroy the node.

The disconnect method already performs the necessary steps, so the delete method can simply call disconnect:

Specializing the dlnode Class

function delete(node)
   disconnect(node);
end

The dlnode class implements a doubly linked list and provides a convenient starting point for creating more specialized types of linked lists. For example, suppose you want to create a list in which each node has a name.

Rather than copying the code used to implement the dlnode class, and then expanding upon it, you can derive a new class from dlnode (i.e., subclass dlnode) to create a class that has all the features of dlnode and more. And because dlnode is a handle class, this new class is a handle class too.

The following class definition shows how to derive the NamedNode class from the dlnode class:

classdef NamedNode < dlnode
   properties
      Name = ''; % property to contain node name
   end 
   methods
      function n = NamedNode (name,data)
         if nargin == 0   % allow for the no argument case
            name = '';
            data = [];
         end
         n = n@dlnode(data); % Initialize a dlnode object
         n.Name = name;
      end 
      function disp(node) % Extend the dlnode disp method
         if (isscalar(node))
            disp(['Node Name: ' n.Name])
            disp@dlnode(node); % Call dlnode disp method
         else
            disp@dlnode(node);
         end
      end
   end % methods
end % classdef

The NamedNode class adds a Name property to store the node name and extends the disp method defined in the dlnode class.

The constructor calls the class constructor for the dlnode class, and then assigns a value to the Name property. The NamedNode class defines default values for the properties for cases when MATLAB calls the constructor with no arguments.

See Basic Structure of Constructor Methods for more information on defining class constructor methods.

Using the NamedNode Class to Create a Doubly Linked List

Use the NamedNode class like the dlnode class, except you specify a name for each node object. For example:

n(1) = NamedNode('First Node',100);
n(2) = NamedNode('Second Node',200);
n(3) = NamedNode('Third Node',300);

Now use the insert methods inherited from dlnode to build the list:

n(2).insertAfter(n(1))
n(3).insertAfter(n(2))

A single node displays its name and data when you query its properties:

>> n(1).Next
ans = 
Node Name: Second Node
Doubly-linked list node with data:
   200
>> n(1).Next.Next
ans = 
Node Name: Third Node
Doubly-linked list node with data:
   300
>> n(3).Prev.Prev
ans = 
Node Name: First Node
Doubly-linked list node with data:
   100

If you display an array of nodes, the NamedNode disp method displays only the dimensions of the array:

>> n
n = 
1x3 array of doubly-linked list nodes

Matlab Implementing Linked Lists

Displaying Fully Commented Example Code

Important Concepts Demonstrated

Encapsulation

Handle Class Behavior

dlnode Class Design

Class Properties

Class Methods

Creating Doubly Linked Lists

Why a Handle Class for Doubly Linked Lists?

Defining the dlnode Class

Class Properties

Creating a Node Object

Disconnecting Nodes

Inserting Nodes

Displaying a Node on the Command Line

Deleting a Node Object

Specializing the dlnode Class

Using the NamedNode Class to Create a Doubly Linked List

You may also like...

Using the Editor and Debugger with Classes

rmpath

for