This is the 11th day of my participation in the Gwen Challenge in November. Check out the details: The last Gwen Challenge in 2021

The introduction

Data structures are containers used to organize and store data in a computer so that we can perform operations efficiently. They are the most basic building blocks of programming. The best-known and most commonly used data structure, besides arrays, stacks, queues, etc., is a very useful data structure called linked lists. However, Swift does not provide a built-in linked list structure, so today we will implement one step by step.

What is a singly linked list

A linked list is a list of linked nodes. A node is a single element that contains a generic value and a pointer to the next node. There are several types of linked lists:

  • Singly linked listsEach node has only one pointer to the next node. Operations can only be delivered in one direction
  • Two-way linked listEach node has two Pointers, one to the next node and one to the previous node. The operation can be done in both forward and backward directions
  • Circular linked listThe next pointer to the last node points to the first node, and the previous pointer to the first node points to the last node

Today we’re going to implement a single linked list in Swift.

Node

Node must be defined as Class. Since it is designed to be a reference, it needs to be a reference type. The Node class has two properties:

  • valueThe generic data type of the actual value of the storage node
  • nextPointer to the next node
class Node<T> {
    var value: T
    var next: Node<T>?

    init(value: T.next: Node<T>? = nil) {
        self.value = value
        self.next = next
    }
}
Copy the code

The list

Unlike Node, a linked list is a value type, defined as a Struct. By default, linked lists have three basic properties:

  • headThe first node in a linked list
  • tailThe last node in the linked list
  • isEmptyWhether the linked list is empty

Of course, you can add other attributes as needed, such as:

  • countThe number of nodes in the linked list
  • descriptionDescription text for linked lists
struct LinkedList<T> {
  var head: Node<T>?
  var tail: Node<T>?

  var isEmpty: Bool { head = = nil }

  init(a){}}Copy the code

Unlike stacks and queues, linked lists do not contain collections of data that can be called and used directly. All nodes in the list must be linked to the next available node, if any.

Push

Adding data to the head of the list means that the current head will be replaced with the new node, which will become the head of the list.

struct LinkedList<T> {

    .
    
    mutating func push(_ value: T) {
        head = Node(value: value, next: head)
        if tail = = nil {
            tail = head

        }
    }
}
Copy the code

By calling push(_ value: T), we create a new node with that value and make it point to the original head. We then replace the head with a new node so that the original head becomes the second node in the list.

Append

Like push, we add data to the end of the list. This means that the current tail will be replaced by the new node, which will become the new tail.

struct LinkedList<T> {

    .

    mutating func append(_ value: T) {
        let node = Node(value: value)
        tail?.next = node
        tail = node
    }
}
Copy the code

By calling append(_ value: T), we create a new node and point the original tail to the new node. Finally, we replace the old tail with the new node, so that the old tail becomes the penultimate node in the list. The new node will be the new tail

Node At

Linked lists cannot be evaluated by subscript index, so we cannot read collections of data like array[0].

struct LinkedList<T> {

    .

    func node(at index: Int) -> Node<T>? {
        var currentIndex = 0
        var currentNode = head
        while currentNode ! = nil && currentIndex < index {
            currentNode = currentNode?.next
            currentIndex + = 1
        }
        return currentNode
    }
}
Copy the code

To get the Node corresponding to an index, you need to traverse.

Insert

As I said before, linked lists cannot be evaluated by index subscripts. Linked lists only know which node is linked to which node. To tell the list to insert a node at a particular location, we need to find the node linked to that location. V requires the above function: node(at index: Int) -> node

?

struct LinkedList<T> {

    .

    func insert(_ value: T.after index: Int) {
        guard let node = node(at: index) else { return }
        node.next = Node(value: value, next: node.next)
    }
}
Copy the code

First, we must find the node at a given location. We’re going to make it point to the new node, and the new node points to the original next node.

Pop

We remove head from the list so that the second node becomes head:

struct LinkedList<T> {

    .

    mutating func pop(a) -> T? {
        defer {
            head = head?.next
            if isEmpty {
                tail = nil}}return head?.value
    }
}
Copy the code

Return the value of the old head and replace the old head with the old next node, so that the old next node becomes head.

Remove Last

Like pop(), this is the end of the deleted list, so the second-to-last node will be the tail.

struct LinkedList<T> {

    .

    mutating func removeLast(a) -> T? {
        guard let head = head else { return nil }
        guard let _ = head.next else { return pop() }

        var previousNode = head
        var currentNode = head

        while let next = currentNode.next {
            previousNode = currentNode
            currentNode = next
        }
        
        previousNode.next = nil
        tail = previousNode
        return currentNode.value
    }
}
Copy the code

But unlike pop(), removing the tail node is a bit more complicated because the tail does not know who the previous node was. We need to traverse the list to find the node before the tail and set it to the tail.

  • If the head isnilDoes that mean that the list is empty and we have nothing to delete and then returnnil
  • ifhead.nextisnil, which means that there is only one node in the linked list and then the header is removed
  • Loop through the list to find the node before the tail and set it to the tail

Remove After

Similar to insert(_ value: T, after index: Int), we need to find the node at the position to be deleted.

struct LinkedList<T> {

    .

    mutating func remove(after index: Int) -> T? {
        guard let node = node(at: index) else { return nil }
            defer {
                if node.next = = = tail {
                tail = node
            }
            node.next = node.next?.next
        }
        return node.next?.value
    }
}
Copy the code

Removing the node at the specified index is a bit tricky, so we basically just skip a node and point to the node after that node.

conclusion

These are the basic properties and functions that singly linked lists usually have. Of course, you can add other properties and functions from these as well.