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
 There is only one first node and last node;
 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 onetoone 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:
 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
 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 nonsequential 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 doublelinked list is to add a pointer field to the singlylinked list to point to the predecessor of the current node. It is used to easily find its predecessor node. Similar to the singlylinked list, it is also divided into a doublelinked list with a leading node and a doublelinked 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(¤tNode.next, ¤tNode.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

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).

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 doublelinked 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
 The number of data elements can be freely expanded
 Insert, delete and other operations do not need to move data, only need to modify the link pointer, the modification efficiency is higher
 Disadvantages:
 Low storage density
 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:
Spacebased comparison
 Storage allocation method: the storage space of the sequence table is statically allocated, and the storage space of the linked list is dynamically allocated
 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)
Timebased comparison:
 Access mode: The sequential table can be accessed randomly or sequentially, and the linked list is sequential access
 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