Example - Implementing Linked Lists :: MATLAB® Classes Overview (MATLAB®)

MATLAB^®

Example — Implementing Linked Lists

On this page…
Displaying Fully Commented Example Code Important Concepts Demonstrated dlnode Class Design Creating Doubly Linked Lists Why a Handle Class for Doubly Linked Lists? Defining the dlnode Class Specializing the dlnode Class

On this page…

Displaying Fully Commented Example Code

Important Concepts Demonstrated

dlnode Class Design

Creating Doubly Linked Lists

Why a Handle Class for Doubly Linked Lists?

Defining the dlnode Class

Specializing the dlnode Class

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 directory named @dlnode and save dlnode.m to this directory. The parent directory of @dlnode must be on the MATLAB path. Alternatively, save dlnode.m to a path directory.

Important Concepts Demonstrated

Encapsulation

This example shows how classes can encapsulate the internal structure used to implement the design goal—a mechanism to implement 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 can be performed on nodes of this class. These methods hide the potentially confusing process of inserting and removing nodes, while at the same time providing and interface that simply performs the operations you need to perform:

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

Each node is implemented 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 object n1, n2, and n3. It also shows how the nodes reference the next and previous node.

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 only the Data property is displayed on the command line
delete — Removed 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:

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

Why a Handle Class for Doubly Linked Lists?

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. Then 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 instance. 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 above.

Note that the handle class defines the eq method, which enables the use of the == operator with all handle objects.

See Comparing Handle and Value Classes for more information on kinds of MATLAB classes.

See The Handle Base Class for more information about the handle class.

Defining the dlnode Class

Assume the following doubly linked list is used in the following examples:

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 the Next and Prev properties can be set only by class methods (SetAccess = private) to prevent 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.

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. When the node is added to a list, the Next and Prev properties are set by the class methods that perform the insertion.

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

Disconnecting Nodes

The disconnect method removes a node from a list and heals the list by connecting the appropriate nodes. Note that disconnect is always called on a node before attempting to connect it to a linked list to ensure a known state for the Next and Prev properties.

function disconnect(node)
   Prev = node.Prev;
   Next = node.Next;
   if ~isempty(Prev)
      Prev.Next = Next;
   end
   if ~isempty(Next)
      Next.Prev = Prev;
   end
   node.Next = [];
   node.Prev = [];
end

First the list is repaired. Assume this example is using n2 from the three-node list discussed above:

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).

Inserting Nodes

There are two methods for inserting nodes into the list—insertAfter and insertBefore. These methods perform similar operations, so only insertAfter is explained 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

The first step is always to ensure the new node is not connected to any other nodes; hence, disconnect is called first. Assuming you are calling insertAfter to insert n2 back into the list after n1:

n2.insertAfter(n1)

n2.Next = n1.Next; % n1.Next is still n3, set n2.Next to n3
n2.Prev = n1;
if n1.Next is not empty, then
   n1.Next.Prev = n2; % n1.Next is n3, so n3.Prev is set to n2
n1.Next = n2; % n1.Next is now set to n2

Displaying a Node on the Command Line

All objects call a default disp function, which displays all object properties and their values on the command line. That is not a useful approach in this case because the Next and Prev properties contain other node objects. Therefore, the dlnode class overloads disp to display only a text message and the value of the Data property.

function disp(node)
   disp('Doubly-linked list node with data:')
   disp(node.Data);
end

Deleting a Node Object

When you define a delete method for a handle class, it is called before destroying the object. dlnode objects are nodes in a doubly linked list, so it is important to disconnect the node before destroying it. Otherwise the links to that node are broken. The disconnect method performs the necessary steps, so the delete method can simply call disconnect:

function delete(node)
   disconnect(node);
end

Specializing the dlnode Class

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 new 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 = '';
   end 
   methods
      function n = NamedNode (name,data)
         if nargin == 0   % to handle the no argument case
            name = '';
            data = [];
         end
         n = n@dlnode(data); % Initialize a dlnode object
         n.Name = name;
      end 
      function disp(n) % Override the dlnode disp method
         disp(['Node Name: ' n.Name])
         disp(['Node Data: ' num2str(n.Data)])
      end
   end % methods
end % classdef

The NamedNode class adds a Name property to store the node name and overrides the disp method defined in the dlnode class. The constructor calls the class constructor for the SimpleNode class, and then assigns a value to the Name property.

Note that the constructor method is designed to handle the zero input argument case by creating an empty cell array, which contains the arguments if there are any and remains empty if there are not. See Basic Structure of Constructor Methods for more information on defining class constructor methods and why a constructor method should be able to handle the case where it is called with no input arguments.

Using the NamedNode Class to Create a Doubly Linked List

Use the NamedNode class in a way very similar to the SimpleNode class. For example:

n1=NamedNode('First Node',100);
n2=NamedNode('Second Node',200);
n3=NamedNode('Third Node',300);

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

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

The nodes display their name and data when querying the properties:

>> n1.Next
ans =
Node Name: Second Node
Node Data: 200
>> n1.Next.Next
ans =
Node Name: Third Node
Node Data: 300
>> n3.Prev.Prev
ans =
Node Name: First Node
Node Data: 100

Example — Representing Structured Data

Example — Class for Graphing Functions