Data structure notes-linear table definition and implementation (Swift)

Data structure notes-linear table definition and implementation (Swift)

Data structure notes series Data Structure Notes - two merged into a sorted linked list ordered

Linear table

A linear table is the most commonly used and simplest data structure.In short, a linear table is an ordered sequence of n data elements.

Features

  1. There is only one first node and last node;
  2. Except for the first and last nodes, the other nodes have only one direct predecessor and one direct successor.

In short, the linear structure reflects the one-to-one logical relationship between nodes. The linear structure includes linear tables, stacks, queues, strings, arrays, etc., among which, the most typical and commonly used

Linear table division

Divided from the storage structure, it can be divided into sequential storage structure called sequential table and chain storage structure called linked list

Sequence table

Storage definition of sequence table

A storage structure in which logically adjacent data elements are stored in physically adjacent storage units. Simply put, logically adjacent, physically adjacent

Features of sequence table:

  1. Use the storage location of the data element to represent the context between adjacent data elements in the linear table, that is, the logical structure of the linear table is consistent with the storage structure
  2. When accessing the linear table, you can quickly calculate the storage address of any data element. Therefore, it can be roughly considered that the time spent on accessing each element is equal

The complexity of the sequence table:

Time complexity: The average time complexity of the search, insert, and delete algorithms of the sequence table is O(n)

Space complexity: The time complexity of the sequence table is O(1)

The advantages and disadvantages of the sequence table:

Advantages: high storage density (storage amount occupied by the node itself/storage amount occupied by the node structure), any element in the table can be accessed randomly

Disadvantages: When inserting or deleting an element, a large number of elements need to be moved, and storage space is wasted. It belongs to a static storage form, and the number of data elements cannot be expanded freely.

Linked list

Features of linked list

The position of the node in the memory is arbitrary, that is, the logically adjacent data elements are not necessarily physically adjacent. The chained representation of the linear table is also called non-sequential mapping or chained mapping.

Node

The storage image of the data element. It consists of two parts : data field and pointer field. Data field : stores element value data. Pointer field : stores the storage location of the immediate subsequent node

Data field Pointer field

Note: == Head pointer, head node, head yuan node == these concepts:

  • Head pointer: is a pointer to the first node in the linked list
  • Header node: refers to the node that stores the first data element a1 in the linked list
  • Head node: It is a node attached before the head node of the linked list; only information such as table flag and table length is empty in the data field. Its function is mainly to facilitate the operation of the linked list

The head node may or may not exist, but the head pointer must be present.

The form of the linked list:

Single list

The node has only a linked list of pointer domains. In addition to the data field, each node also contains a pointer field to point to its successor nodes.

Data field Pointer field

Storage image of singly linked list

  • A singly linked list with a head node: the head pointer points to its head node, the value range of the head node can contain no information, and the information is stored from the subsequent nodes of the head node
  • A singly linked list without a head node: the head pointer points to its head node

Realization of singly linked list

Whether the singly linked list is empty
func isEmpty() -> Bool {
        return head == nil
    }
 
Get the head yuan node
public var first:Node?{
        return head
    }
 
Get the end node
public var last:Node? {
        if var node = head {
            while case let next? = node.next {
                node = next
            }
            return node
        } else {
            return nil
        }
    }
 
The length of the linked list
public var count:Int {
        if var node = head {
            var c = 1
            while case let next? = node.next {
                node = next
                c += 1
            }
            return c
        } else {
            return 0
        }
    }
 
Node acquisition
func getNode(atIndex index:Int) -> Node? {
        if index >= 0 {
         var node = head
            var i = index
            while node != nil {
                if i == 0 {
                    return node
                }
                i -= 1
                node = node?.next
            }
        }
        return nil
    }
 
Adding a linked list

public func append(_ value: T) {
        let newNode = SLNode(value: value)
        if let lastNode = last {
            lastNode.next = newNode
        } else {
            head = newNode
        }
    }
   // 
    public func append(_ values:Array<T>) {
        for value in values {
            append(value)
        }
    }
 
The insertion of the linked list is inserted at the index node
public func insertNode(atIndex index:Int,value:T) {
        let oldNode = getBeforeNode(atIndex: index)
        let newNode = SLNode(value: value)
        if index > 0 {
            if let old = oldNode {
                newNode.next = old.next
                old.next = newNode
            } else {
                append(value)
            }
        } else if (index == 0 ) {
            newNode.next = head
            head = newNode
        } else {
            append(value)
        }
    }
 
Singly linked list delete

       
public func removeNode(atIndex index:Int) {
        let beforeNode = getBeforeNode(atIndex: index)
        if let before = beforeNode {
            before.next = before.next?.next
        }
    }
    
   // 
    public func removeAll() {
        head = nil
    }
 

Double linked list

There are two linked lists of pointer fields. A double-linked list is to add a pointer field to the singly-linked list to point to the predecessor of the current node. It is used to easily find its predecessor node. Similar to the singly-linked list, it is also divided into a double-linked list with a leading node and a double-linked list without a leading node. .

Pointer field Data field Pointer field

Realization of doubly linked list

Define a node of a doubly linked list

//    
public class DLNode<T> {
    var value: T
    var next :DLNode?// 
    weak var previous :DLNode?//
    public init(value:T) {
        self.value = value
    }
}
 

Define a doubly linked list

public final class DoubleLinkList<T> {
   //  DLNode<T>   Node
    public typealias Node = DLNode<T>
  //
    fileprivate var head:Node?
        public init() {}
    }
    
 

Whether the doubly linked list is empty

    public var isEmpty:Bool {
        return head == nil//
    }
 

Doubly linked list to get the head node

    public var first:Node?{
        return head
    }
    
 

Doubly linked list to get the end node

The node pointed to by the next pointer of the end node must be empty. So start traversing from the first node, if next is empty than the end node

    public var last:Node? {
        if var node = head {
            while case let next? = node.next {
                node = next
            }
            return node
        } else {
            return nil
        }
    }

 

The length of the doubly linked list

Start traversing from the head node, and continue to traverse to the end node, until the traversal is completed, the length of each node is increased by one

    public var count:Int {
        if var node = head {
            var c = 1
            while case let next? = node.next {
                node = next
                c += 1
            }
            return c
        } else {
            return 0
        }
    }
 

Lookup of doubly linked list:

Starting from the head node, the search complexity is O(n)

  public func node(atIndex index: Int) -> Node? {
        if index >= 0 {
            var node = head
            var i = index
            while node != nil {//
                if i == 0 {
                    return node
                }
                i -= 1
                node = node!.next
            }
        }
        return nil
    }
 

Insertion of doubly linked list

Insert a node at a certain position. Steps of inserting a doubly linked list;

    public func insert(_ node: Node, atIndex index: Int) {
        let oldNode = getNode(atIndex: index)
        let newNode = DLNode(value: node.value)
        newNode.previous = oldNode?.previous
        oldNode?.previous?.next = newNode
        newNode.next = oldNode
        oldNode?.previous = newNode
        if oldNode?.previous == nil {
            head = newNode
        }
    }
    
 

Deletion of doubly linked list

To delete a node in the linked list, the steps are as follows

@discardableResult public func remove(atIndex index: Int) -> T {
        let node = self.getNode(atIndex: index)
        assert(node != nil)
        return remove(node: node!)
    }
    
    
    
    
    
@discardableResult public func remove(node: Node) -> T {
        let prev = node.previous
        let next = node.next
        
        if let prev = prev {
            prev.next = next
        } else {
            head = next
        }
        next?.previous = prev
        
        node.previous = nil
        node.next = nil
        return node.value
    }
 

Doubly linked list flip

public func reverse() {
        var node = head
        while let currentNode = node {
            node = currentNode.next// node
            swap(&currentNode.next, &currentNode.previous)// 
            head = currentNode
        }
    }
 
  • [x] The above is the operation of doubly linked list. The operation of singly linked list, single cyclic linked list and doubly cyclic linked list can refer to the operation of doubly linked list.

Analysis of Operational Efficiency of Linked List

  1. Search: Because the linear linked list can only be accessed sequentially, that is, when searching, it needs to start from the head pointer. The time complexity of searching is O(n).

  2. Insertion and deletion: Because the linear linked list does not need to move elements, as long as the pointer is modified, the time complexity is O(1) in general.

However, if you want to insert or delete operations in the singly linked list, the time complexity is O(n) because you need to find the predecessor node from the beginning.

Circular singly linked list

The last pointer field of the singly linked list points to the first node in the linked list. The circular singly linked list can be realized from any node to visit any node in the linked list.

  • [x] Note: The first node is mentioned here instead of the head node because, if the circular singly linked list is the leading node, the pointer field of the last node must point to the head node, if the circular singly linked list If there is no head node, the last pointer field should point to the head node

Circular doubly linked list

The linked list end to end is derived from a double-linked list. That is, the successor node of the terminal node is set as the first node (head node or head node), and the successor node of the first node in the linked list is set as the terminal node.

The advantages and disadvantages of linked lists

  • advantage
  1. The number of data elements can be freely expanded
  2. Insert, delete and other operations do not need to move data, only need to modify the link pointer, the modification efficiency is higher
  • Disadvantages:
  1. Low storage density
  2. The access efficiency is not high, and sequential access must be used, that is, when accessing data elements, they can only be accessed in the order of the linked list (follow the vine)

Comparison of sequence list and linked list:

Space-based comparison

  1. Storage allocation method: the storage space of the sequence table is statically allocated, and the storage space of the linked list is dynamically allocated
  2. Storage density: (Storage density = storage amount occupied by the node value range/total storage amount occupied by the node structure), the storage density of the sequence table = 1 the storage density of the linked list <1 (because there are pointers stored in the nodes area)

Time-based comparison:

  1. Access mode: The sequential table can be accessed randomly or sequentially, and the linked list is sequential access
  2. The number of elements moved when inserting and deleting: the sequence table needs to move nearly half of the elements on average, the linked list does not need to be moved, only the pointer needs to be modified

More detailed code