Связанный список - это линейная структура данных. Вместо того, чтобы хранить данные в каком-то месте, его элементы связываются с помощью указателей.
Каждый элемент в связанном списке представлен узлом. Узел состоит из данных и указывает (или ссылки) на следующий узел.
Есть три типа связанных списков:
- Односвязный список
- Двусвязный список
- Список с круговыми ссылками
В этом руководстве мы рассмотрим алгоритмы односвязных списков, такие как:
- Добавить
- Вставка
- Удаление
- Печать
Начнем с создания класса узла как универсального типа.
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
