Doubly LinkedLists
A doubly LinkedList is the same as a singly LinkedList, with the exception that each node has a reverse pointer in addition to the forward pointer. In other words, each node points to the next node as well as the previous node.
Image courtesy GeeksForGeeks
Circular LinkedLists
In Singly Linked Lists, each node only points to the next node in the list, but what does the last node point to? Nothing. The last node has a NULL pointer, so it doesn’t point to any memory address.
Image courtesy GeeksForGeeks
How do they work?
If you want to access item D, the computer starts at Head, and continues in one direction down the list until it gets to item D. If you wanted to access item C next in a Singly Linked List, you’d have to start at the Head again to go down to C. In a Doubly Linked List, you’d simply be able to go backwards by one (since each node would have a reverse pointer as well as a forward pointer) to reach C.
However, if you wanted to go to item A, in a Doubly Linked List, you’d either have to go back all the way down the line (C to B to A), or start at the Head again and go to A.
That’s where Circular Linked Lists come in: in these lists, the last node points back to the first node. In Java,
Important Note:
There is no CircularLinkedList class built into Java. Similarly, there is no SinglyLinkedList class, because the LinkedList class is already made to be doubly-linked. In the next couple sections, we will write the code to implement a Singly Linked List class from scratch, and we will transform the Singly Linked List into a Circular Linked List by changing the pointer of the last node.
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.