Linked list according to Wikipedia:
It's a linear collection of data elements, whose order is not given by their physical placement in memory. Instead, each element points to the next. It is a data structure consisting of a collection of nodes that together represent a sequence.
Types of a linked list.
- Singly.
- Doubly.
- Circular.
- And many more.
Operations that we are going to perform.
- Add a node from left/right.
- Remove Node from left/right.
- Size of the list.
- Search data in the list.
Here we 'll see only a Singly list.
Let's define the structure for List
struct Node {
var data: T?
var next: Node?
init[_ data: T] {
self.data = data
}
}
As soon as to define this structure, you 'll hit with compilation error.
Due to the nature of struct this issue obvious, as the compiler must know the size of struct in compile time. In this case, struct refers to itself which means there no definite size.
To resolve it, just change from struct [value type] to class [reference type].
class Node{
Here we are using a generic type called so that we can hold any type of data in the list.
Define an enum as direction for node manipulation.
enum ListDirection {
case left
case right
}
Define a structure for SinglyLinkedList & functions to implement as shown below.
struct SinglyLinkedList {
// If nil, then there is NO node in list sequence.
var firstNode: Node?
// Adds data/Item by creating node from specified direction.
mutating func add[anItem item: T, from d: ListDirection] { }
// Remove item from from specified direction.
mutating func remove[from d: ListDirection] -> Node? { }
// fetch number of nodes available in linked list
func getListSize[] -> Int? { }
// Search for item/data existance in list, returns true or false
func search[anItem item: T?] -> Bool { }
// Displays content of list
func showListContent[] { }
}
Let's start the implementation of those function, the explanation will be available inline.
add[anItem:from:] function
// Adds data/Item by creating node from a specified direction.
mutating func add[anItem item: T, from d: ListDirection] {
// Create node by supplied data, to be added in list
let newNode = Node[item]
// Validation check for node list does NOT exist, if true then, make new node as firstNode
if firstNode == nil {
self.firstNode = newNode
}
else {
// Obtain firstNode reference.
var tempNode = self.firstNode
if d == .left { // Validation check for data insertion from Left side.
// Make tempNode as next sequence for newly created node.
newNode.next = tempNode
// Make newNode as first node, so that new data empbed on left side.
self.firstNode = newNode
}
else if d == .right { // Validation check for data insertion from Right side.
// Note that the first node is never manipulated in this clause.
// Traverse till it reaches nil
while tempNode?.next != nil {
tempNode = tempNode?.next
}
// Then insert new node from right side.
tempNode?.next = newNode
}
}
}
Now create an instance of a singly linked list & start adding items in it.
var ll = SinglyLinkedList[]
ll.add[anItem: 10, from: .left]
ll.add[anItem: 20, from: .right]
ll.add[anItem: 30, from: .left]
ll.add[anItem: 40, from: .left]
ll.add[anItem: 50, from: .right]
ll.add[anItem: 60, from: .right]
Once we added items there is no way we can see it in action, for that we required a showListContent[] function. Below is the implementation of it.
// Displays content of list
func showListContent[] {
// Visible string to display sequence of data in list
var visibleNodeSequence: String = ""
var tempNode = self.firstNode
// Travese till reaches end of list
while tempNode != nil {
if let str = tempNode?.data {
visibleNodeSequence.append[contentsOf: String[describing:str]]
visibleNodeSequence.append[contentsOf: tempNode?.next != nil ? " -> " : ""]
}
// Incrementing by pointing to next node
tempNode = tempNode?.next
}
print[visibleNodeSequence]
}
// Display content of list
ll.showListContent[]
On console, you can see output like this.
remove[from:] -> Node? function
// Remove item from from specified direction.
mutating func remove[from d: ListDirection] -> Node? {
var nodeToBeRemoved: Node?
// return nil, incase of NO sequence exist
if self.firstNode == nil {
return nil
}
var nextNode = self.firstNode
if d == .left {
// Makes sure firstNode's next node becomes firstNode. so that firstNode from left side can be removed.
self.firstNode = nextNode?.next
nodeToBeRemoved = nextNode
}
else if d == .right {
// Maintains a previous node, so that connection for node to be removed is deleted.
var prevnode: Node? = self.firstNode
// Traverse till it reaches nil node
while nextNode?.next != nil {
// Both points to same node, then next node is incremented to point to next of next
prevnode = nextNode
nextNode = nextNode?.next
}
// Connection deleting for node to be removed
prevnode?.next = nil
nodeToBeRemoved = nextNode
}
return nodeToBeRemoved
}
getListSize[]->Int? function
// fetch number of nodes available in linked list
func getListSize[] -> Int? {
// Validation check for first node is nil.
guard firstNode != nil else { return nil }
var tempNode = firstNode
// Maintian a counter to loop
var noOfNodes = 0
// Traverse till it reaches nil node
while tempNode != nil {
// If not nil then increment counter
noOfNodes += 1
// Increment node by pointing to next node
tempNode = tempNode?.next
}
return noOfNodes
}
// Get size of linked list
ll.getListSize[]
search[anItem:] -> Bool function
// Search for item/data existance in list, returns true or false
func search[anItem item: T?] -> Bool {
guard firstNode != nil else { return false }
var tempNode = self.firstNode
while tempNode != nil {
if tempNode?.data == item {
// Once item exist return true.
return true
}
// Increment node by pointing to next node
tempNode = tempNode?.next
}
return false
}
// Searches item 40 in list
ll.search[anItem: 40]
Video liên quan