Support us


to write
more tutorials




to create new
visualizers




to keep sharing
free knowledge
for you


every dollar helps
Need help with a programming assignment? Get affordable programming homework help.

Singly-linked list. Internal representation.

Every node of a singly-linked list contains following information:

  • a value (user's data);
  • a link to the next element (auxiliary data).

Sketchy, it can be shown like this:

Singly-linked list implementation

First node called head and no other node points to it. Link to the head is usually stored it the class, which provides an interface to the resulting data structure. For empty list, head is set to NULL.

Also, it makes sense to store a link to the last node, called tail. Though no node in the list can be accessed from the tail (because we can move forward only), it can accelerate an add operation, when adding to the end of the list. When list is big, it reduces add operation complexity essentially, while memory overhead is insignificant. Below you can see another picture, which shows the whole singly-linked list internal representation:

Singly-linked list extended implementation

Code snippets

Commonly, the whole structure of singly-linked list is put into two classes. Main class, SinglyLinkedList, is a public interface and SinglyLinkedListNode mean for private use inside the main class. Because of SinglyLinkedListNode is auxiliary class, it's not necessary to encapsulate its fields (make them private). Notice, that SinglyLinkedList interface class may be replaced by another one, such as a Stack class, while internal implementation of the stack remains a singly-linked list.

Java implementation

public class SinglyLinkedListNode {

      public int value;

      public SinglyLinkedListNode next;

 

      public SinglyLinkedListNode(int value) {

            this.value = value;

            next = null;

      }

}

 

public class SinglyLinkedList {

      private SinglyLinkedListNode head;

      private SinglyLinkedListNode tail;

 

      public SinglyLinkedList() {

            head = null;

            tail = null;

      }

}

C++ implementation

class SinglyLinkedListNode {

public:

      int value;

      SinglyLinkedListNode *next;

 

      SinglyLinkedListNode(int value) {

            this->value = value;

            next = NULL;

      }

};

 

class SinglyLinkedList {

private:

      SinglyLinkedListNode *head;

      SinglyLinkedListNode *tail;

public:

      SinglyLinkedList() {

            head = NULL;

            tail = NULL;

      }

}

Recommended books

  1. Cormen, Leiserson, Rivest. Introduction to algorithms. (Theory)
  2. Aho, Ullman, Hopcroft. Data Structures and Algorithms. (Theory)
  3. Robert Lafore. Data Structures and Algorithms in Java. (Practice)
  4. Mark Allen Weiss. Data Structures and Problem Solving Using C++. (Practice)

Contribute to AlgoList

Liked this tutorial? Please, consider making a donation. Contribute to help us keep sharing free knowledge and write new tutorials.


Every dollar helps!

Partners Ads        garden furniture        traffic management        

Leave a reply

Your name (optional):
Your e-mail (optional):
Message: