Class to Implement Linked Lists

Class Definition Code

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

For the class definition code listing, see dlnode Class Definition

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.

dlnode Class Design

dlnode is a class for creating doubly linked lists in which each node contains:

  • Data array

  • Handle to the next node

  • Handle to the previous node

Each node has methods that enables the node to be:

  • Inserted before a specified node in a linked list

  • Inserted after a specific node in a linked list

  • Removed from a 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 list with three-nodes 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 — Construct a node and assign the value passed as an input to the Data property

  • insertAfter — Insert this node after the specified node

  • insertBefore — Insert this node before the specified node

  • removeNode — Remove this node from the list and reconnect the remaining nodes

  • clearList — Remove large lists efficiently

  • delete — Private method called by MATLAB when deleting the list.

Create Doubly Linked List

Create a node by passing the node's data to the dlnode class constructor. For example, these statements create three nodes with data values 1, 2, and 3:

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

Build these nodes into a doubly linked list using the class methods designed for this purpose:

n2.insertAfter(n1) % Insert n2 after n1
n3.insertAfter(n2) % Insert n3 after n2

Now the three nodes are linked:

n1.Next % Points to n2
ans = 

  dlnode with properties:

    Data: 2
    Next: [1x1 dlnode]
    Prev: [1x1 dlnode]
n2.Next.Prev % Points back to n2
ans = 

  dlnode with properties:

    Data: 2
    Next: [1x1 dlnode]
    Prev: [1x1 dlnode]
n1.Next.Next % Points to n3
ans = 

  dlnode with properties:

    Data: 3
    Next: []
    Prev: [1x1 dlnode]
n3.Prev.Prev % Points to n1
ans = 

  dlnode with properties:

    Data: 1
    Next: [1x1 dlnode]
    Prev: []

Why a Handle Class for Linked Lists?

Each node is unique in that no two nodes can be previous to or next to the same node.

For example, 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.

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.

Related Information

For more information on handle classes, see Comparing Handle and Value Classes and The Handle Superclass.

dlnode Class Definition

This section describes the implementation of the dlnode class.

 dlnode Code

Class Properties

Only dlnode class methods can set the Next and Prev properties because these properties have private set access (SetAccess = private). Using private set access prevents client code from performing any incorrect operation with these properties. The dlnode class methods perform all the operations that are allowed on these nodes.

The Data property has public set and get access, allowing you to query and modify the value of Data as required.

Here is how the dlnode class defines the properties:

properties
   Data
end
properties(SetAccess = private)
   Next = dlnode.empty;
   Prev = dlnode.empty;
end

Construct a Node Object

To create a node object, specify the node's data as an argument to the constructor:

function node = dlnode(Data)
% Construct a dlnode object.
   if nargin > 0
      node.Data = Data;
   end
end

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

function insertAfter(newNode, nodeBefore)
   % Insert newNode after nodeBefore.
   removeNode(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 removeNode method to ensure that the new node is not connected to any other nodes. Then, insertAfter 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—n3.

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:

  • Set nnew.Next to n1.Next (n1.Next is n2):

    nnew.Next = n1.Next;
  • Set nnew.Prev 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;

Remove a Node

The removeNode method removes a node from a list and reconnects the appropriate nodes. The insertBefore and insertAfter methods always call removeNode on the node to insert before attempting to connect it to a linked list.

Calling removeNode ensures the node is in a known state before assigning it to the Next or Prev property:

function removeNode(node)
   % Remove a node from a linked list.
   if ~isscalar(node)
      error('Input 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 = dlnode.empty;
   node.Prev = dlnode.empty;
end

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

n2.removeNode;

removeNode 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):

n2.Next = dlnode.empty;
n2.Prev = dlnode.empty;

Delete a Node

To delete a node, call the removeNode method on that node. The removeNode method disconnects the node and reconnects the list before allowing MATLAB to destroy the removed node. MATLAB destroys the node once references to it by other nodes are removed and the list is reconnected.

For example, suppose you create a list with ten nodes and save the handle to the head of the list:

head = dlnode(1);
for i = 10:-1:2
   new = dlnode(i);
   insertAfter(new,head);
end

Now remove the third node (Data property assigned the value 3):

removeNode(head.Next.Next)

Now the third node in the list has a data value of 4:

>> head.Next.Next
ans = 

  dlnode with properties:

    Data: 4
    Next: [1x1 dlnode]
    Prev: [1x1 dlnode]

And the previous node has a Data value of 2:

>> head.Next
ans = 

  dlnode with properties:

    Data: 2
    Next: [1x1 dlnode]
    Prev: [1x1 dlnode]

Delete the List

When you create a linked list and assign a variable that contains, for example, the head or tail of the list, clearing that variable causes the destructor to recurse through the entire list. With large enough list, clearing the list variable can result in MATLAB exceeding its recursion limit.

The clearList method avoids recursion and improves the performance of deleting large lists by looping over the list and disconnecting each node. clearList accepts the handle of any node in the list and removes the remaining nodes.

function clearList(node)
   % Clear the list before
   % clearing list variable
   if ~isscalar(node)
      error('Input must be scalar')
   end
   prev = node.Prev;
   next = node.Next;
   removeNode(node)
   while ~isempty(next)
      node = next;
      next = node.Next;
      removeNode(node);
   end
   while ~isempty(prev)
      node = prev;
      prev = node.Prev;
      removeNode(node)
   end
end

For example, suppose you create a list with a large number of nodes:

head = dlnode(1);
for k = 100000:-1:2
   nextNode = dlnode(k);
   insertAfter(nextNode,head)
end

The variable head contains the handle to the node at the head of the list:

head
head = 

  dlnode with properties:

    Data: 1
    Next: [1x1 dlnode]
    Prev: []
head.Next
ans = 

  dlnode with properties:

    Data: 2
    Next: [1x1 dlnode]
    Prev: [1x1 dlnode]

You can call clearList to remove the whole list:

clearList(head)

The only nodes that have not been deleted by MATLAB are those for which there exists an explicit reference. In this case, those references are head and nextNode:

head
head = 

  dlnode with properties:

    Data: 1
    Next: []
    Prev: []
nextNode
nextNode = 

  dlnode with properties:

    Data: 2
    Next: []
    Prev: []

You can removed these nodes by clearing the variables:

clear head nextNode

The delete Method

The delete method simply calls the clearList method:

methods (Access = private)
   function delete(node)
      % Delete all nodes
      clearList(node)
   end
end

The delete method has private access to prevent users from calling delete when intending to delete a single node. MATLAB calls delete implicitly when the list is destroyed by the clearList method.

To delete a single node from the list, use the removeNode method.

Specialize 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). You can create a class that has all the features of dlnode and also defines its own additional features. And because dlnode is a handle class, this new class is a handle class too.

NamedNode Class Definition

Open class definition file in the MATLAB editor. 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 @NamedNode and save NamedNode.m to this folder. The parent folder of @NamedNode must be on the MATLAB path. Alternatively, save NamedNode.m to a path folder.

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
            name = '';
            data = [];
         end
         n = n@dlnode(data);
         n.Name = name;
      end % NamedNode
   end % methods
end % classdef

The NamedNode class adds a Name property to store the node name.

The constructor calls the class constructor for the dlnode class, and then assigns a value to the Name property.

Use NamedNode to Create a Doubly Linked List

Use the NamedNode class like the dlnode class, except that 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 = 

  NamedNode with properties:

    Name: 'Second Node'
    Data: 200
    Next: [1x1 NamedNode]
    Prev: [1x1 NamedNode]
n(1).Next.Next
ans = 

  NamedNode with properties:

    Name: 'Third Node'
    Data: 300
    Next: []
    Prev: [1x1 NamedNode]
n(3).Prev.Prev
ans = 

  NamedNode with properties:

    Name: 'First Node'
    Data: 100
    Next: [1x1 NamedNode]
    Prev: []
Was this topic helpful?