Definition
Linked List a linear data structure like Arrays, but its internal is completely different compared to other data structures. Let’s first have a visual look how the data structure looks like
As you can see in the above image Linked List maintains a list of objects linked to them, as also the name suggests the same approach. To conclude some characteristics in Linked List;
- Each node has a next pointer/reference to the next or previous object then we are iterating through these references,
- The last nodes are usually null,
- However, the next/previous references do not refer to null in certain times(in the following chapters, I’ll demonstrate the reasons)
Linked list is used in some data structures like Queues and Stacks internally. Check them out separately and see how Linked List fits in their requirements.
Advantages
- No size limitation compared to the arrays,
- It is not costly to insert and remove in between nodes. As such operation is very costly in arrays with larger data sets, because all the elements will be shifted,
Disadvantages
- Random data access is not possible, the whole data structure must be traversed to access the designated object,
- Storage to the next and previous nodes takes up some memory space.
Time and Space Complexity
image courtesy of bigocheatsheet.com
Types of Linked Lists
Linked List has some varieties of implementations that often confuse us. I’ll show all the implementations in sub sections with visuals, descriptions and codes that will let you interact more and apprehend the slightest differences better.
Singly Linked List
In a Singly Linked List the traversal is unidirectional, each node refers to the next node in the link, and there is no reference to previous nodes. The last node’s next refers to Null.
See the Implementation “SinglyLinkedList.java” and the Unit Test “SinglyLinkedListUnitTest.java” to apprehend all the operations and internals of the Singly Linked List.
Doubly Linked List
Doubly Linked List maintains a bidirectional path, thus it contains next and previous links, where next refers to the next node, and previous refers to the previous node. This maintenance comes with an extra overhead. Last of all, first node’s previous and last node’s next are Null.
See the Implementation “DoublyLinkedList.java” and the Unit Test “DoublyLinkedListUnitTest.java” to apprehend all the operations and internals of the Doubly Linked List.
Circular Linked List
Circular Linked List is the last variation of the implementation. I would like to call the Circular Linked List as the spiced up version of the Singly and Doubly Linked List implementations in my own terms. In addition, as the name suggests, the basic internal is that the Linked List is being circular. Now time to clear out the 3rd element in the definition and explain
two distinct characteristics in the Circular Linked List;
- The head and the tail of the data structure don’t point to NULL, but head’s previous reference, points to tail and tail’s next reference points to the head,
- Circular List can be made using Singly or Doubly Linked List implementations.
Doubly Circular Linked List
Operations
Operation description goes here
- isEmpty: Checks whether the Linked List is empty,
- insertFirst: Inserts the given Node to the head of Linked List,
- insertAfter: Inserts the given Node after the existing Node in Linked List,
- insertLast: Inserts the given Node at the end of Linked List,
- deleteFirst: Deletes the Node in the head of Linked List,
- deleteNode: Deletes the given Node in Linked List,
- deleteLast: Deletes the given Node from the end of Linked List,
- containsIterativeSearch: Iteratively searches Linked List,
- containsRecursiveSearch: Recursively searches Linked List.
Code
The code can be also found in my Github Repository @ https://github.com/tugrulaslan/BlogCodeSnippets/tree/master/DataStructures To see how the code works, you can also check its Unit Test.