Implementing Linked Lists with Classes

The DoublyLinkedList class represents a doubly linked list made up of instances of the Node class. Each Node instance contains data as well as references to the node before it and after it in the list.

`Node` Class Design

The Node class implements an individual node as a handle object with three properties:

Data — Data stored in the node
Next — A reference to the next node in the list, with SetAccess restricted to the DoublyLinkedList class
Previous — A WeakHandle reference to the previous node in the list, with SetAccess restricted to the DoublyLinkedList class

Node is implemented as a handle class because each node is unique. No node in a list can have the same Next and Previous property values as another node in the list because then the two nodes would occupy the same place in the list.

classdef Node < handle
    properties
        Data
    end
    properties (SetAccess=?DoublyLinkedList)
        Next Node = Node.empty
    end
    properties (SetAccess=?DoublyLinkedList,WeakHandle)
        Previous Node = Node.empty
    end
    methods
        function node = Node(data)
            node.Data = data;
        end
    end
    methods (Access=?DoublyLinkedList)
        function delete(~)
        end
    end
end

The SetAcess of Next and Previous is restricted to instances of DoublyLinkedList. This restriction helps prevent external code from unintentionally breaking links between nodes. The Previous property is also defined with the WeakHandle attribute. Using a weak handle reference helps simplify cleanup, because only strong references affect the lifecycle of an object. Having two nodes point to each other with strong references creates a reference cycle that requires more work to clear. For more information on weak references, see Weak References.

This diagram shows three doubly linked nodes, labeled n, n +1, and n + 2, in a list. The blue arrows represent strong references in the Next property of each node. The dashed green arrows represent weak references in the Previous property of each node.

`DoublyLinkedList` Class Design

The DoublyLinkedList class creates and manages a doubly linked list made up of instances of Node. The class defines three properties:

Head — The first node in the list
Tail — The last node in the list
ListLength — The length of the list

The methods of DoublyLinkedList include:

DoublyLinkedList — Construct an empty list (no arguments) or a list with nodes populated with data from an input array.
insertBefore — Insert a node at the beginning of the list or before a specified node.
insertAfter — Insert a node at the end of the list or after a specified node.
removeNode — Remove a node from the list and reconnect the surrounding nodes.
delete — Delete the list and all Node instances contained in it.

For the full code of the class, see Complete DoublyLinkedList Class Code.

Create and Manage a Doubly Linked List

Construct a `DoublyLinkedList` Instance

The constructor for DoublyLinkedList has two options. The no-argument option creates a list with no nodes, with both Head and Tail properties set to empty Node arrays.

The second option takes a vector as input and creates a Node instance for each value in the vector. The nodes are connected from the head to the tail of the list in the same order as the values in the vector. The constructor performs these steps:

Create a Node instance and assign the first value of the vector to the Data property of that node.
Set the Head and Tail properties to a Node that stores the first value in the input vector in its Data property. If the input vector has only one value, only one node is created and its head and tail are the same.
Step through the remaining values in the input vector. Use the insertAfter method to add a node corresponding to each value to the list. See Insert a Node into the List for more information.

function list = DoublyLinkedList(varargin)
   narginchk(0,1);
   if (nargin == 0)
      return
   elseif (nargin == 1)
      nodeValues = varargin{1};
      mustBeNonempty(nodeValues);
      mustBeVector(nodeValues);

      headNode = Node(nodeValues(1));
      list.Head = headNode;
      list.Tail = headNode;

      currNode = list.Head;
      for i = 2:numel(nodeValues)
         data = nodeValues(i);
         nextNode = Node(data);
         list.insertAfter(nextNode,currNode);
         currNode = nextNode;
      end
   end
end

Construct a list using the vector [1 3 5] as input.

myList = DoublyLinkedList([1 3 5])

myList = 

  DoublyLinkedList with properties:

          Head: [1×1 Node]
          Tail: [1×1 Node]
    ListLength: 3

Insert a Node into the List

You can add nodes to an existing list using the insertAfter and insertBefore methods. Both methods take a list, a node to insert, and optionally, a node currently in the list as the position for insertion. If you do not specify the position, the default values are the tail and head nodes, respectively.

Both methods use similar processes. The process for insertAfter is:

If the node to insert is already at the specified position, do nothing.
If the specified position is not a node in the list, return an error.
Call removeNode on the node to be inserted. If the node is currently somewhere else in the list, removeNode sets its Previous and Next properties to empty to prepare to move it to a new position in the list. If the node is owned by a different list, removeNode does not set Previous and Next to empty, and the method errors. (For more information on removeNode, see Remove a Node from the List.)
Insert the node, accounting for edge cases like insertion into an empty list or insertion as the new head or tail of the list.

function list = insertAfter(list,nodeToInsert,nodePos)
   arguments
      list
      nodeToInsert (1,1) Node
      nodePos {mustBeA(nodePos,"Node"),mustBeScalarOrEmpty(nodePos)} = list.Tail
   end

   if (nodeToInsert == nodePos)
      return
   end

   if ~isempty(nodePos) && ~list.containsNode(nodePos)
      error("The specified node is not in the list.");
   end

   list.removeNode(nodeToInsert);
   if ~isempty(nodeToInsert.Previous) || ~isempty(nodeToInsert.Next)
      error("The specified node to insert is already owned by a different list.");
   end

   if isempty(nodePos)
      list.Head = nodeToInsert;
      list.Tail = nodeToInsert; 

   elseif list.isTail(nodePos)
      list.Tail = nodeToInsert;
      nodeToInsert.Previous = nodePos;
      nodePos.Next = nodeToInsert;

   else 
      currNext = nodePos.Next;

      nodeToInsert.Next = currNext;
      currNext.Previous = nodeToInsert;

      nodeToInsert.Previous = nodePos;
      nodePos.Next = nodeToInsert;
   end
end

Insert a node with Data set to 2 into the list after the head.

myList.insertAfter(Node(2),myList.Head)

ans = 

  DoublyLinkedList with properties:

          Head: [1×1 Node]
          Tail: [1×1 Node]
    ListLength: 4

Verify that the node after the list head, myList.Head.Next, is the new node.

myList.Head.Next

ans = 

  Node with properties:

        Data: 2
        Next: [1×1 Node]
    Previous: [1×1 Node]

insertAfter performs these steps to add the node and reconnect the existing nodes:

Node(2).Next is set to Head.Next.
The Previous property of the node that used to follow Head is set to Node(2).
Node(2).Previous is set to the originally specified position node, in this case Head.
The Next property of Head is set to Node(2).

Remove a Node from the List

The removeNode method takes a node as an argument, disconnects it from the list, and returns that node instance in case you have further use for it. removeNode performs these steps:

Confirm that the list contains the node to be removed. If the node is not in the list, do nothing.
If the removed node is the head of the list, reset Head to the next node. Otherwise, set the Next property of the node before the removed node to the node after the removed node.
If the removed node is the tail of the list, reset Tail to the previous node. Otherwise, set the Previous property of the node after the removed node to the node before the removed node.
Disconnect the node from the list by setting the Next and Previous properties of the node to empty.

function nodeToRemove = removeNode(list,nodeToRemove)
   arguments
      list
      nodeToRemove (1,1) Node
   end

   if ~list.containsNode(nodeToRemove) 
      return
   end
            
   nodeBefore = nodeToRemove.Previous;
   nodeAfter = nodeToRemove.Next;
 
   if list.isHead(nodeToRemove)
      list.Head = nodeAfter;
   else
      nodeBefore.Next = nodeAfter;
   end

   if list.isTail(nodeToRemove)
      list.Tail = nodeBefore;
   else
      nodeAfter.Previous = nodeBefore;
   end     

   nodeToRemove.Previous = Node.empty;
   nodeToRemove.Next = Node.empty;
end

The next-to-last node from myList has Data set to 3. Remove it from the list.

oldNode = myList.removeNode(myList.Tail.Previous)

oldNode = 

  Node with properties:

        Data: 3
        Next: [0×0 Node]
    Previous: [0×0 Node]

removeNode performs these steps to remove the node and reconnect the existing nodes:

The Next property of the node before the removed node is set to the node after, which in this case is Tail.
The Previous property of the node after the removed node is set to the node before, which in this case is Tail.Previous.Previous.
The Previous and Next properties of the removed node are set to Node.empty.

Delete a List

The overridden delete method for a list starts at the head of the list and repeatedly calls removeNode to delete all the nodes one by one.

function delete(list)
   while ~isempty(list.Head)
      oldHead = list.removeNode(list.Head);
      delete(oldHead);
   end
end

Delete myList. Any remaining handles to nodes that were in myList are now deleted handles.

delete(myList);
myList

myList = 

  handle to deleted DoublyLinkedList

Complete `DoublyLinkedList` Class Code

classdef DoublyLinkedList < handle
    properties (SetAccess=private)
        Head Node = Node.empty
        Tail Node = Node.empty
    end

    properties (Dependent)
        ListLength
    end

    methods
        function list = DoublyLinkedList(varargin)
            narginchk(0,1);
            if (nargin == 0)
                return
            elseif (nargin == 1)
                nodeValues = varargin{1};
                mustBeNonempty(nodeValues);
                mustBeVector(nodeValues);

                headNode = Node(nodeValues(1));
                list.Head = headNode;
                list.Tail = headNode;

                currNode = list.Head;
                for i = 2:numel(nodeValues)
                    data = nodeValues(i);
                    nextNode = Node(data);
                    list.insertAfter(nextNode,currNode);
                    currNode = nextNode;
                end
            end
        end

        function list = insertBefore(list,nodeToInsert,nodePos)
            arguments
                list
                nodeToInsert (1,1) Node
                nodePos {mustBeA(nodePos,"Node"),mustBeScalarOrEmpty(nodePos)} = list.Head
            end

            if (nodePos == nodeToInsert)
                return
            end

            if ~isempty(nodePos) && ~list.containsNode(nodePos)
                error("The specified position is not in the list.");
            end

            list.removeNode(nodeToInsert);
            if ~isempty(nodeToInsert.Previous) || ~isempty(nodeToInsert.Next)
                error("The specified node to insert is already owned by a different list.");
            end

            if isempty(nodePos)
                list.Head = nodeToInsert;
                list.Tail = nodeToInsert;

            elseif list.isHead(nodePos)
                list.Head = nodeToInsert;
                nodeToInsert.Next = nodePos;
                nodePos.Previous = nodeToInsert;

            else
                currPrev = nodePos.Previous;

                nodeToInsert.Previous = currPrev;
                currPrev.Next = nodeToInsert;

                nodeToInsert.Next = nodePos;
                nodePos.Previous = nodeToInsert;
            end
        end

        function list = insertAfter(list,nodeToInsert,nodePos)
            arguments
                list
                nodeToInsert (1,1) Node
                nodePos {mustBeA(nodePos,"Node"),mustBeScalarOrEmpty(nodePos)} = list.Tail
            end

            if (nodeToInsert == nodePos)
                return
            end

            if ~isempty(nodePos) && ~list.containsNode(nodePos)
                error("The specified position is not in the list.");
            end

            list.removeNode(nodeToInsert);
            if ~isempty(nodeToInsert.Previous) || ~isempty(nodeToInsert.Next)
                error("The specified node to insert is already owned by a different list.");
            end

            if isempty(nodePos)
                list.Head = nodeToInsert;
                list.Tail = nodeToInsert;

            elseif list.isTail(nodePos)
                list.Tail = nodeToInsert;
                nodeToInsert.Previous = nodePos;
                nodePos.Next = nodeToInsert;

            else
                currNext = nodePos.Next;

                nodeToInsert.Next = currNext;
                currNext.Previous = nodeToInsert;

                nodeToInsert.Previous = nodePos;
                nodePos.Next = nodeToInsert;
            end
        end

        function nodeToRemove = removeNode(list,nodeToRemove)
            arguments
                list
                nodeToRemove (1,1) Node
            end

            if ~list.containsNode(nodeToRemove) 
                return
            end
            
            nodeBefore = nodeToRemove.Previous;
            nodeAfter = nodeToRemove.Next;
   
            if list.isHead(nodeToRemove)
                list.Head = nodeAfter;
            else
                nodeBefore.Next = nodeAfter;
            end

            if list.isTail(nodeToRemove)
                list.Tail = nodeBefore;
            else
                nodeAfter.Previous = nodeBefore;
            end     

            nodeToRemove.Previous = Node.empty;
            nodeToRemove.Next = Node.empty;
        end

        function len = get.ListLength(list)
            curr = list.Head;
            len = 0;
            while ~isempty(curr)
                len = len+1;
                curr = curr.Next;
            end
        end

        function delete(list)
            while ~isempty(list.Head)
                oldHead = list.removeNode(list.Head);
                delete(oldHead);
            end
        end
    end

    % Utility methods
    methods (Access=private)
        function isPresent = containsNode(list,node)
            isPresent = false;
            currNode = list.Head;

            while ~isempty(currNode)
                if currNode == node
                    isPresent = true;
                    return
                end
                currNode = currNode.Next;
            end
        end

        function isHead = isHead(list,node)
            isHead = (node == list.Head);
        end

        function isTail = isTail(list,node)
            isTail = (node == list.Tail);
        end
    end
end

Implementing Linked Lists with Classes

`Node` Class Design

`DoublyLinkedList` Class Design

Create and Manage a Doubly Linked List

Construct a `DoublyLinkedList` Instance

Insert a Node into the List

Remove a Node from the List

Delete a List

Complete `DoublyLinkedList` Class Code

See Also

Topics

Implementing Linked Lists with Classes

Node Class Design

DoublyLinkedList Class Design

Create and Manage a Doubly Linked List

Construct a DoublyLinkedList Instance

Insert a Node into the List

Remove a Node from the List

Delete a List

Complete DoublyLinkedList Class Code

See Also

Topics

`Node` Class Design

`DoublyLinkedList` Class Design

Construct a `DoublyLinkedList` Instance

Complete `DoublyLinkedList` Class Code