Data Structure series: LinkedList
In this article you are going to understand LinkedList data structure from real life use cases to actual implementation.
Starting with some factual information about LinkedList data structure
- Linked List contains data and reference ofdata in each of it’s node.
- Linked list is the second most used data structure after array.
- Linked list is a linear data structure.
- Linked List elements are storing in the form of non-contiguous memory allocations.
- Insertion & Deletion is cheaper than array i.e. O(1) time complexity.
Real time scenario’s based on Linked List
Scenario 1: In real life the comonly things i can imagine for linked list application is connected coaches of trains where one coach is connected with their next and prev coach.
Scenario 2: Music player is another Realtime example where when you pick up any album then for example you have selected 3rd music from the music list of the album then once you click Next or Prev it will go next as 4th song or Prev as 2nd song. and if you go Next Next Next untill album song not finished you will be able to listen next by next songs respectively.
Scenario 3: Image Viewer is an another example where you can select any image our of multiple images in an folder and then either press Prev or Next, the viewer will display Prev or Next image respectively.
Let’s visualize Queue insertion and deletion operations in linked list from head and tail
here below gif is to demonstrate operations of Linked List
- Insertion : Add an element at the beginning
- Deletion: Delete an element at the beginning
- Search: search an element on the basis of search key.
Let’s design and implement your own LinkedList
In LinkedList the first thing that you need to create a data class for handling node
data class Node<T>(
var value: T,
var next: Node<T>? = null
) {
override fun toString(): String {
return if (next != null) {
"$value -> ${next.toString()}"
} else {
"$value"
}
}
fun printInReverse() {
next?.printInReverse()
if (next != null) {
print(" -> ")
}
print(value.toString())
}
}First you need an blueprint of your operations that gonna be handled by an interface so my interface name is ILinkedList.kt
interface ILinkedList<T> {
fun isEmpty(): Boolean
fun push(value: T)
fun append(value: T)
fun nodeAt(index: Int): Node<T>?
fun printHead(): T?
fun printTail(): T?
fun insert(value: T, afterNode: Node<T>?): Node<T>
}then make an implementation class to handle all these operations
class LinkedList<T> : ILinkedList<T> {
private var head: Node<T>? = null
private var tail: Node<T>? = null
private var size = 0
override fun printHead(): T? = head?.value
override fun printTail(): T? = tail?.value
override fun isEmpty() = size == 0
override fun toString(): String {
return if (isEmpty()) {
EMPTY_LIST
} else {
head.toString()
}
}
override fun append(value: T) {
if (isEmpty()) {
push(value)
return
}
val newNode = Node(value = value)
tail?.next = newNode
tail = newNode
size++
}
override fun nodeAt(index: Int): Node<T>? {
var currentNode = head
var currentIndex = 0
while (currentNode != null && currentIndex < index) {
currentNode = currentNode.next
currentIndex++
}
return currentNode
}
override fun push(value: T) {
head = Node(value = value, next = head)
if (tail == null) {
tail = head
}
size++
}
override fun insert(value: T, afterNode: Node<T>?): Node<T> {
if (tail == afterNode) {
append(value)
return tail!!
}
val newNode = Node(value = value, next = afterNode?.next)
afterNode?.next = newNode
size++
return newNode
}
companion object {
const val EMPTY_LIST = "empty list"
}
}Now let’s go to check your implementation by LinkedListRunner.kt file
fun main() {
val list = LinkedList<Int>()
list.apply {
push(55)
push(7)
push(69)
push(11)
push(99)
println("head value is: ${printHead()}")
println("tail value is: ${printTail()}")
println("-------------------after appending new node value = 200 ----------------------------")
append(200)
println("head value is: ${printHead()}")
println("tail value is: ${printTail()}")
println(list)
println("-------------------insert at where value is = 7 ----------------------------")
insert(300,nodeAt(1))
println("head value is: ${printHead()}")
println("tail value is: ${printTail()}")
println(list)
}
}And the results are below
If you are preparing for interviews then below questions are top most questions asked based on Linked List
- Design Linked List
- Reverse LinkedList
- Delete Node in a Linked List
- Intersection of Two Linked Lists
- Merge In Between Linked Lists
- Middle of the Linked List
- Implement LRU cache [hard level]
Few solutions that you can see below but I would suggest before moving to solutions, please try once from yourself :)
Solution: Reverse LinkedList
private fun reverseList(head: ListNode?): ListNode? {
if (head == null) return null
var currentNode = head
var previousNode: ListNode? = null
var reversedNode: ListNode? = null
while (currentNode != null) {
val next = currentNode.next
if (next == null) {
reversedNode = currentNode
}
currentNode.next = previousNode
previousNode = currentNode
currentNode = next
}
return reversedNode
}Solution: Delete Node in a Linked List
fun deleteNode(node: ListNode?) {
node?.let {victim ->
victim.next?.let {nextNode ->
victim.`val` = nextNode.`val`
victim.next = nextNode.next
}
}
}Solution: Intersection of Two Linked Lists
fun getIntersectionNode(headA:ListNode?, headB:ListNode?):ListNode? {
var currA = headA
var currB = headB
while(currA != currB){
currA = if (currA == null) headB else currA.next
currB = if (currB == null) headA else currB.next
}
return currA
}References
- https://leetcode.com/
- https://kotlinlang.org/docs/collections-overview.html
- https://medium.com/@myofficework000/data-structure-series-queue-data-structure-62b1c5bd335
Thank you for reading my article. I really appreciate 👏 your response.