Singly Linked List

1. What is a Singly Linked List?

A Singly Linked List is a linked list in which data can be traversed naturally in a single direction usually forward.

The SinglyLinkedList class contains only one data item: a reference to the first node of the list. This reference is called first. It’s the only permanent information the list maintains about the location of any of the links. It finds the other links by following the chain of references from first, using each link’s next field:

A high level view of Singly Linked List would be something like:

 

2. Node

In Singly Linked List, each node has a next pointer which points to the following node. The next pointer of the last node points to null which means the end of the linked list.

The node object in Singly Linked List can have multiple data fields and one reference fields to hold the reference to the next node in the list. For keeping things simple we will use a node with single data field of type int.

 

3. Basic operations

The basic operations supported by a Singly linked list are Insertion, Deletion and Traversal. Insertion and Deletion can have their own flavour as we will soon discover.

3.1 Insertion

a. At the beginning

While inserting at the beginning, there are two possibilities:

  1. The list is empty
  2. The list has some existing elements.

If, the list is empty, we just need to:

  1. Create a new node.
  2. Set its next pointer to null.
  3. Make first point to it.

and we are done.

If, the list is non-empty, it means first is already pointing at the first node of the list. So, all we need to do is:

  1. Create a new node.
  2. Set its next pointer to the node where first is pointing.
  3. Make first point to it.

Pay attention to newNode.setNext(first).

When the list is empty, first is null. It has never been assigned any value. So, when we set newNode’s pointer to it we basically point it to null.

But once a node is added to the linked list, first is not pointing to null anymore. It points to the first node of our SinglyLinkedList. So, when you add a second node to the list, the newNode doesn’t point to null anymore, it points to the first node of the list and then first points to the newly added node.

b. At the end

Similar to insertion, while we try to insert at the end, the list may be empty or non-empty.
If the list is empty, we just add the node, the way we added in addAtBeginning(), if not, we use an additional pointer current and move it till the end of the list and add the node there.

 

 

c. At specified position

To, insert a node at specified position we will make two assumptions:

1. If the specified position is less than 1, we will add the node at beginning.
2. If the specified position is greater than the list-size, we will add the node at the end.

You can also, throw an exception or prompt user to provide a valid position.

 

 

 

3.2 Deletion

a. At the beginning

Similar to insertion, there are two possibilities when we delete a node from the beginning:

  1. The list is empty
  2. The list has some existing elements.

If, the list is empty, we will just print the message – “The list is empty.” and return. Throwing an exception is also an option.

If, the list has only one element, we simply set first = null; and return.

If, the list has multiple elements, we:

  1. Create a temporary node, temp, which will point to the same node as pointed by first.
  2. Move first to the next node.
  3. Dispose the node pointed by temp.

 

b. At the end

 

Similar to previous case, the list could be empty, have single element and have multiple elements.

First two cases are self-explanatory and for the third one i.e in case of multiple elements, all we need to do is:

Traverse the list till the end (using current) and while traversing we also maintain the previous node address (using temp). Once we reach the end we make temp point to null and dispose current node.

 

c. At specified position

Now, this case differs very slightly with the previous one. Here the node to be deleted could be the first one, the last one or some intermediate one.

In case, it is the intermediate one, we need to traverse till the specified position and also maintain the address of the node previous to the node-to-be-deleted. Then we need to make previous node point to the node currently being pointed to by node-to-be-deleted and dispose off the node-to-be-deleted.

3.3 Traversal

Traversing a Singly Linked List is pretty simple as compared to insertion and deletion because to traverse the list we simply:

  1. Follow the current pointer till the end of the list.
  2. Display the contents of the nodes as they are traversed.

4. Source Code

This is the zipped source file with all the code. You can unzip it and put it in any of your project in your IDE and run as a java application or you can also run it using command prompt/terminal. In case you are using command prompt, make sure you compile it first ;).

SinglyLinkedListDemo.java.zip

4. Output