Code 4 Tomorrow

Now you try!

As you learned in the Circular LinkedLists section, the only difference between Circular Linked Lists and Singly Linked Lists is that the last node of CLLs points to the head node again. We can simply modify the SLL implementation, so that last.next points to head instead of to null. It’s also more time efficient to store the location of the last node, instead of storing the location of head, so that you don’t have to traverse all the way down the list to add something to the end.

The new add() method looks similar to the previous one, but we set new_node.next to the head. Notice how we only store a reference to the last node, and we replaced “head” with “last.next” because it’s a circular list.


class CircularLinkedList {
	Node last;
	
	public void add(int data); {
		// Create a new node with given data
		Node new_node = new Node(data);

		// Make new_node point back to head to complete the circle
		new_node.next = new_node:

		// If the Linked List is empty, then make the new node as head
		if (last == null) {
			last = new_node;
		} else {
			// Else insert new_node at the end
			new_node.next = last.next;
			last.next = new_node;
			last = new_node;
		}
	}
}

We need to change the toString() method, as well, again changing “head” to “last.next.”


@Override
public String toString() {
	// For empty lists
	if (last == null)
		return "{}";

	String str = "{";

	// Traverse the list until you reach last
	Node current = last.next;
	while(current != last) {
		str += "" + current.data + ", ";
		current = current.next;
	}
	str += current.data + "}";
	return str;
}

Here’s some test code and it’s output:


class Main {
	public static void main(String[] args) {
		CircularLinkedlist = last new CircularLinkedList();
		System.out.println(list);
		list.add(1);
		System.out.println(list);
		list.add(27);
		System.out.println(list);
		list.add(-3);
		System.out.println(list);
	}
}

output:


{}
{1}
{1, 27}
{1, 27, -3}

Now you try!

If you play around with your newly-created class, it should display the same result as the SinglyLinkedList. However, there are some benefits to being able to iterate through CircularLinkedLists continuously. For example, if you had a list of tasks that you wanted your computer to continually cycle through, you could store the tasks in a CircularLinkedList, and this would be much more time efficient than other methods of storage.

Previous Section

3️⃣

16.3 Do It Yourself! - SinglyLinkedList

Next Section

5️⃣

16.5 Benefits of LinkedLists

⚖️

Copyright © 2021 Code 4 Tomorrow. All rights reserved. The code in this course is licensed under the MIT License. If you would like to use content from any of our courses, you must obtain our explicit written permission and provide credit. Please contact classes@code4tomorrow.org for inquiries.

16.4 Do it Yourself! - CirclyLinkedList

Now you try!

Previous Section

Next Section