What is a Linked List?
A linked list is a common data structure that is similar to an array, but its order is based on pointers to the next element in memory instead of using physical placement (indices).
A linked list has two main components:
- ListNode class: This class has a
val
property that represents the value and anext
property that represents a pointer to the next element in memory. - LinkedList class: This class stores a collection of
ListNode
elements and provides operations likeadd to tail
andadd to head
.- The
add to tail
operation takes O(n) time because it needs to iterate through the list to find the last element. - The
add to head
operation takes O(1) time because it only needs to set the next pointer of the new node to the current head and update the head with the new node.
- The
Where can it be used?
A linked list can be used in stacks, queues, and lists.
Code Example
final class ListNode {
let val: Int
var next: ListNode?
init(val: Int, next: ListNode? = nil) {
self.val = val
self.next = next
}
}
final class LinkedList {
private(set) var head: ListNode?
init(head: ListNode? = nil) {
self.head = head
}
func addToTail(_ newNode: ListNode?) {
if self.head == nil {
self.head = newNode
return
}
var node: ListNode? = self.head
while node?.next != nil {
node = node!.next
}
node?.next = newNode
}
func addToHead(_ newNode: ListNode?) {
newNode?.next = self.head
self.head = newNode
}
}