Overview :
LinkedLists are often used as a replacement for arrays when the need for dynamic resizing arises. This is because arrays are fixed in size, so if you need to add or remove elements from the middle of the array, you have to copy all of the elements that follow the insertion or removal point. With a linked list, you can simply add or remove the element without having to copy any data.
LinkedList:
1. A linked list is a linear data structure.
2. Each element of the linked list, is called a node.
3. Node contains data and a reference (or pointer) to the next node in the list.
4. Linked lists are a dynamic data structure, meaning that they can grow and shrink as needed.
This makes them well-suited for applications where the size of the data set is not known in advance or where the data set is frequently changing.
Linked lists are made up of nodes, each of which contains two parts:
Data: The data stored in the node.
Pointer: A pointer to the next node in the list.
data class Node(val data:Int){
val next: Node? = null
}This is the generalized way :
data class Node1<T>(val data:T){
val next: Node<T>? = null
}Here is an example of a linked list:
Head -> Node 1 -> Node 2 -> Node 3 -> Tail
Types of Linked Lists:
- Singly Linked list
2. Doubly Linked list
3. Circular Linked list
See in images :
Key points :
- The first node in the list is called the head node.
- Linked lists can be traversed in both directions means Forward or Backward.
- Forward traversal is the most common way to traverse a linked list.
- To traverse a linked list forward, start at the head node and follow the pointer to the next node until you reach the tail node.
- Linked lists are a versatile data structure that can be used in a variety of applications.
- They are particularly well-suited for applications where the size of the data set is not known in advance or where the data set is likely to change frequently.
Operations: There are several operations to make a linked list.
- Create Node :
// Create Nodes
override fun createNode(data:Int) = Node(data)Insertion/Add: Adding a new node to the list.
override fun addNode(node: Node<T>) {
val newNode = createNode(node as T)
// check for head is null
if (head == null) {
head = newNode
return
}
// traverse to the end
var traverse = head
while (traverse?.next != null) {
traverse = traverse.next
}
// assign in the last
traverse?.next = newNode
// update count
size++
}Deletion: Removing a node from the list.
A. Delete linked list via position :
override fun deleteNode(position: Int) {
// validate position value first
// it should be in 0 to linkedlist size
if (position in 0..size) {
// check for head is null
if (head == null) return
// check for head value if position value is 0 means need to delete head.
if (position == 0) head = head?.next
// traverse 0 to the end
var traverse = head
var previous : Node <T>? = null
var curPosition = 0
while (traverse != null) {
// compare traverse data position and given position as input is same or not
if (curPosition == position) {
previous?.next = traverse.next
break
}
previous = traverse
traverse = traverse.next
curPosition++
}
// delete count
size--
}
}B. Delete linked list as given node :
override fun deleteNode(node: Node<T>) {
// check for head is null
if (head == null) return
// check for head value if position value is 0 means need to delete head.
if (head?.data == node.data) head = head?.next
// traverse 0 to the end
var traverse = head
var previous : Node <T>? = null
while (traverse != null) {
// compare traverse data and given node is equal or not
if (traverse.data == node.data) {
previous?.next = traverse.next
break
}
previous = traverse
traverse = traverse.next
}
// down size
size--
}Traversal: Visiting each node in the list.
override fun traverse() {
// check for head is null
if(head == null) return
// traverse to the end
var traverse = head
while(traverse !=null){
println("${traverse.data}")
traverse = traverse.next
}
}Searching: Finding a particular node in the list.
override fun search(data: Node<T>):Node<T>? {
var resultItem : Node<T>? = null
// check for head is null
if(head == null) return resultItem
// traverse to the end
var traverse = head
while(traverse !=null){
if(traverse.data == data.data){
resultItem = traverse
break
}
traverse = traverse.next
}
return resultItem
}Fetching position node :
override fun get(position: Int): Node<T>? {
var resultItem: Node<T>? = null
// check for head is null
if (head == null) return resultItem
// traverse 0 to the end
var traverse = head
var curPosition = 0
// traverse loop either reach to given position or end of linkedlist
while (curPosition !=position && traverse !=null) {
traverse = traverse.next
curPosition ++
}
if (curPosition == position) {
resultItem = traverse
}
return resultItem // this return position node or null in case of item not found
}Calculate Size:
- You can either manage size by the counter (increase while adding a new node and decrease while deleting a node ) Prefered this way because its have no special iteration.
- Or calculate size by traverse
fun calculateSize():Int {
var count = 0
// check for head is null
if(head == null) return count
// traverse to the end
var traverse = head
while(traverse !=null){
count++
traverse = traverse.next
}
return count
}Full Code :
data class Node<T>(val data: T) {
var next: Node<T>? = null
}
interface LinkedList<T> {
fun createNode(data: T): Node<T>
fun addNode(data: T)
fun addNode(node: Node<T>)
fun deleteNode(position: Int)
fun deleteNode(node: Node<T>)
fun traverse()
fun search(node: Node<T>): Node<T>?
fun get(position: Int): Node<T>?
fun reverse(): Node<T>? // return reverseHead node after reverse linkedList
fun size(): Int
}
class LinkedListImp<T> : LinkedList<T> {
var head: Node<T>? = null
var size = 0
override fun createNode(data: T): Node<T> {
return Node(data)
}
override fun addNode(data: T) {
addNode(createNode(data))
}
override fun addNode(node: Node<T>) {
println("add new node ${node.data}")
val newNode = createNode(node as T)
// check for head is null
if (head == null) {
head = newNode
return
}
// traverse to the end
var traverse = head
while (traverse?.next != null) {
traverse = traverse.next
}
// assign in the last
traverse?.next = newNode
// update count
size++
}
override fun deleteNode(position: Int) {
println("deleted node at position ${position}")
// validate position value first
// it should be in 0 to linkedlist size
if (position in 0..size) {
// check for head is null
if (head == null) return
// check for head value if position value is 0 means need to delete head.
if (position == 0) head = head?.next
// traverse 0 to the end
var traverse = head
var previous : Node<T>? = null
var curPosition = 0
while (traverse != null) {
// compare traverse data position and given position as input is same or not
if (curPosition == position) {
previous?.next = traverse.next
break
}
previous = traverse
traverse = traverse.next
curPosition++
}
// delete count
size--
}
}
override fun deleteNode(node: Node<T>) {
println("deleted node data ${node.data}")
// check for head is null
if (head == null) return
// check for head value if position value is 0 means need to delete head.
if (head?.data == node.data) head = head?.next
// traverse 0 to the end
var traverse = head
var previous : Node<T>? = null
while (traverse != null) {
// compare traverse data and given node is equal or not
if (traverse.data == node.data) {
previous?.next = traverse.next
break
}
previous = traverse
traverse = traverse.next
}
// down size
size--
}
override fun traverse() {
println("traverse : ")
// check for head is null
if (head == null) return
// traverse to the end
var traverse = head
while (traverse != null) {
println("${traverse.data}")
traverse = traverse.next
}
}
override fun search(node: Node<T>): Node<T>? {
println("search and target is ${node.data} ")
var resultItem: Node<T>? = null
// check for head is null
if (head == null) return resultItem
// traverse to the end
var traverse = head
while (traverse != null) {
if (traverse.data == node.data) {
resultItem = traverse
break
}
traverse = traverse.next
}
return resultItem
}
override fun get(position: Int): Node<T>? {
println("get value at position $position >> ")
var resultItem: Node<T>? = null
// check for head is null
if (head == null) return resultItem
// traverse 0 to the end
var traverse = head
var curPosition = 0
// traverse loop either reach to given position or end of linkedlist
while (curPosition !=position && traverse !=null) {
traverse = traverse.next
curPosition ++
}
if (curPosition == position) {
resultItem = traverse
}
return resultItem // this return position node or null in case of item not found
}
override fun reverse(): Node<T>? {
println("reverse >> ")
// check for head is null
if (head == null) head
// traverse to the end and put value into stack
val nodeStack = Stack<Node<T>>()
var traverse = head
while (traverse != null) {
nodeStack.push(traverse)
traverse = traverse.next
}
// set first item as head
val reverseHead = nodeStack.pop()
traverse = reverseHead
while (!nodeStack.empty()){
val node = nodeStack.pop()
node.next = null // so that its break
traverse?.next = node
traverse = traverse?.next
}
head = reverseHead
return reverseHead
}
override fun size() = size
fun calculateSize(): Int {
var count = 0
// check for head is null
if (head == null) return count
// traverse to the end
var traverse = head
while (traverse != null) {
count++
traverse = traverse.next
}
return count
}
fun println(msg:String){
Log.d("linkedlist", msg)
}
}Validate Implementation :
fun checkLinkedList() {
val linkedList: LinkedList<Int> = LinkedListImp()
linkedList.addNode(15)
linkedList.addNode(7)
linkedList.addNode(48)
linkedList.addNode(6)
linkedList.addNode(13)
linkedList.traverse()
linkedList.deleteNode(4)
linkedList.traverse()
linkedList.reverse()
linkedList.traverse()
}Output :
Benefits :
1. They are dynamic in size, so you can add or remove elements without having to resize the data structure.
2. They are efficient for the insertion and removal of elements from any position in the sequence.
3. They are easy to implement.
Drawbacks :
1. They can be slower than arrays for accessing elements in sequential order.
2. They can take up more memory than arrays because each node in the linked list contains a reference to the next node.
3. They are not as efficient for accessing elements in a specific position in the sequence.
Real-world applications and future use :
- Web browsers: Linked lists are used to store the history of visited pages. This allows users to easily go back to pages they have previously visited.
- Email clients: Linked lists are used to store the list of emails in a mailbox. This allows users to easily navigate through their emails.
- Operating systems: Linked lists are used to store the list of open files. This allows the operating system to easily keep track of which files are in use.
- Databases: Linked lists can be used to store data in a non-sequential manner. This can be useful for storing data that needs to be easily modified, such as a list of users or a list of products.
- Compilers: Linked lists are used to store the parse tree of a program. This allows the compiler to easily analyze the program and generate code.
Conclusions :
Overall, linked lists are a versatile data structure that can be used for a variety of tasks. They are particularly well-suited for applications where dynamic resizing is required or where efficient insertion and removal of elements from any position in the sequence is important.
Complexity :
Time: Worse O(n), Average :O(n)
Space: O(n)
Thanks to :
