Связанный список - это линейная структура данных. Вместо того, чтобы хранить данные в каком-то месте, его элементы связываются с помощью указателей.
Каждый элемент в связанном списке представлен узлом. Узел состоит из данных и указывает (или ссылки) на следующий узел.
Есть три типа связанных списков:
- Односвязный список
- Двусвязный список
- Список с круговыми ссылками
В этом руководстве мы рассмотрим алгоритмы односвязных списков, такие как:
- Добавить
- Вставка
- Удаление
- Печать
Начнем с создания класса узла как универсального типа.
public class Node<T> { var value: T var next: Node<T>? init(value: T) { self.value = value } }
Теперь создайте класс SingleLinkedList<T>
, в котором мы будем добавлять, вставлять или удалять элементы.
class SingleLinkedList<T>{ var head: Node<T> public var isLinkedListEmpty:Bool { return head == nil } public var firstItem: Node<T>? { return head } }
isLinkedListEmpty
- это свойство, которое проверяет, является ли LinkedList
пустым или нет. Если голова равна нулю, LinkedList
пусто.
Добавление элемента / узла в односвязный список
Функции добавления добавят новый узел в конец односвязного списка, и для этого мы должны пройти по связанному списку, используя временную ссылку на узел заголовка с именем temp
.
Если мы обнаружили, что ссылка temp
равна нулю, это означает, что мы достигли конца односвязного списка. По этой ссылке мы можем добавить наш новый узел.
public func append(value: T) { let newNode = Node(value: value) if var temp = head { while temp.next != nil { temp = temp.next! } temp.next = newNode } else { head = newNode } }
Вставка элемента / узла в какую-либо позицию в односвязном списке
Чтобы вставить элемент в определенную позицию, сначала нам нужно установить next
ссылку предыдущего узла на новый элемент и установить next
нового элемента на текущий элемент, присутствующий в этой позиции.
Добавьте следующую функцию вставки в вышеупомянутый класс односвязного списка.
func insert(data : T, at position : Int) { let newNode = Node(value: data) if (position == 0) { newNode.next = head head = newNode } else { var previous = head var current = head for _ in 0..<position { previous = current current = current?.next } newNode.next = previous?.next previous?.next = newNode } }
Удаление узла в позиции из односвязного списка
Чтобы удалить узел, нам нужно установить ссылку предыдущего узла на next
узла, который нужно удалить.
Добавьте следующую функцию удаления в класс односвязного списка выше.
func deleteNode(at position: Int) { if head == nil{ return } var temp = head if (position == 0) { head = temp?.next return } for _ in 0..<position-1 where temp != nil { temp = temp?.next } if temp == nil || temp?.next == nil{ return } let nextToNextNode = temp?.next?.next temp?.next = nextToNextNode }
Печать элементов односвязного списка
func printList() { var current: Node? = head while (current != nil) { print("SLL item is: \(current?.value as? String ?? "")") current = current?.next } }
Объединение всех вышеперечисленных функций в нашем классе односвязного списка:
class SingleLinkedList<T> { var head: Node<T>? public var isEmpty: Bool { return head == nil } public var first: Node<T>? { return head } public func append(value: T) { let newNode = Node(value: value) if var temp = head { while temp.next != nil { temp = temp.next! } temp.next = newNode } else { head = newNode } } func insert(data : T, at position : Int) { let newNode = Node(value: data) if (position == 0) { newNode.next = head head = newNode } else { var previous = head var current = head for _ in 0..<position { previous = current current = current?.next } newNode.next = previous?.next previous?.next = newNode } } func deleteNode(at position: Int) { if head == nil{ return } var temp = head if (position == 0) { head = temp?.next return } for _ in 0..<position-1 where temp != nil { temp = temp?.next } if temp == nil || temp?.next == nil{ return } let nextToNextNode = temp?.next?.next temp?.next = nextToNextNode } func printList() { var current: Node? = head //assign the next instance while (current != nil) { print("SLL item is: \(current?.value as? String ?? "")") current = current?.next } } }
Теперь выполните указанные выше функции:
let sll = SingleLinkedList<String>() sll.append(value:"Kim" ) sll.append(value: "Nik") sll.append(value: "Ishu") sll.printList() // First Print sll.insert(data:"Vijay" , at: 1) sll.printList() . // Second Print sll.deleteNode(at: 2) sll.printList() . // Third Print
Результат будет:
// First Print SLL item is: Kim SLL item is: Nik SLL item is: Ishu //Second Print (Inserting string "Vijay" at position 1) SLL item is: Kim SLL item is: Vijay SLL item is: Nik SLL item is: Ishu // Third Print (Deleting Node at Position 2) SLL item is: Kim SLL item is: Vijay SLL item is: Ishu