Skip to main content
Lesson 30 - Linked Lists
ZIPPDF (letter)
Lesson MenuPreviousNext
  
Implementing Linked Lists page 5 of 9

  1. In this section, we will look at the implementation of a linked list of ListNode objects. This class encapsulates the list operations that maintain the links as the list is modified. To keep the class simple, we will implement only a singly linked list, and the list class will supply direct access only to the first list element.

  2. The SinglyLinkedList class holds a reference first to the first ListNode (or null, if the list is completely empty). Access to the first node is provided by the getFirst method. If the list is empty, a NoSuchElementException is thrown.

    class SinglyLinkedList
    {
      private ListNode first;
    
      public SinglyLinkedList()
      {
        first = null;
      }
    
      public Object getFirst()
      {
        if (first == null)
        {
          throw new NoSuchElementException();
        }
        else
          return first.getValue();
      }
    }
  3. Additional nodes are added to the head of the list with the addFirst method. When a new link is added to the list, it becomes the head of the list, and the link that the old list head becomes the next link:

    class SinglyLinkedList
    {
      ...
      public void addFirst(Object value)
      {
        first = new ListNode(value, first);
      }
      ...
    }
  4. The statement ListNode(value, first) invokes the constructor. The line of code

    first = new ListNode(value, first);

    is broken down as follows:

    1. The new command allocates enough memory to store a ListNode
    2. The new ListNode will be assigned the values of value and first.
    3. The address of this newly constructed ListNode is assigned to first
    4. It is important to understand the old and new values of first



  5. When value = 1, first = null. A new node is constructed with the values 1 and null. first points to this new node. In a sense, the constructor provides a new node between the variable first and the node which first used to reference.

    before the call of the constructor

    call the constructor, first is passed as a null value

    first is changed, references the newly constructed node


  6. When value = 2, first is already pointing to the first node of the linked list. When the constructor is called, the new node is constructed and placed between first and the node first used to point to.



    The value of first passed to the ListNode constructor is used to initialize the next field of the new node.


Lesson MenuPreviousNext
Contact
 ©ICT 2003, All Rights Reserved.