线性结构 数组与链表

线性结构 数组与链表

线性结构

线性数据结构有两端，有时被称为左右，某些情况被称为前后。你也可以称为顶部和底部，名字都不重要。将两个线性数据结构区分开的方法是添加和移除项的方式，特别是添加和移除项的位置。例如一些结构允许从一端添加项，另一些允许从另一端移除项。

数组或列表

数组(Array)是编程界最常见的数据结构，有些编程语言被称作位列表(List)。几乎所有编程语言都原生内置数组类型，只是形式向略有不同，因为数组是最简单的内存数据结构。

数组的定义是：一个存储元素的线性集合(Collection)，元素可以通过索引(Index)来任意存取，索引通常是数字，用来计算元素之间存储位置的偏移量。

链表

数组的缺点：要存储多个元素，数组(或列表)可能是最常见的数据结构。但是数组不总是组织数据的最佳结构。在大多数编程语言中，数组的大小是固定的，所以当数组被填满时，再要加入新的元素会非常困难。并且从数组起点或中间插入或移除元素的成本很高，因为需要将数组中的其他元素向前后平移。

链表(Linked list)中的元素在内存中不是连续存放的。链表是由一组节点(Node)组成的集合，每个节点由元素本身和一个指向下一个元素的引用(也被称作链接或指针)组成。相对于数组，链表的好处在于，添加或移除元素的时候不需要移动其他元素。

链表的种类

单向链表(Singly linked list)：是最基本的链表，每个节点一个引用，指向下一个节点。单向链表的第一个节点称为头节点(head node)，最后一个节点称为尾节点(tail node)，尾节点的引用为空（None），不指向下一个节点。

双向链表(Doubly linked list)和单向链表的区别在于，在链表中的节点引用是双向的，一个指向下一个元素，一个指向上一个元素。

循环链表(Circular linked list)和单向链表类似，节点类型都一样。唯一的区别是 ，链表的尾节点引用指向头节点。

双向循环链表：类似于双向链表，尾节点的后置引用指向头节点，头节点的前置引用指向尾节点。

单向链表的操作

Python实现单向链表

# python3
class Node:
    def __init__(self, value=None, next=None):
        self.value = value
        self.next = next


class LinkedList:
    def __init__(self):
        self.head = None
        self.tail = None
        self.size = 0

    def append(self, value):
        node = Node(value)
        if self.head is None:
            self.head = node
            self.tail = node
        else:
            self.tail.next = node
            self.tail = node
        self.size += 1

    def insert(self, index, value):
        if 0 <= index <= self.size:
            node = Node(value)
            current = self.head
            previous = Node(next=current)
            count = 0
            while count < index:
                previous = current
                current = current.next
                count += 1
            previous.next = node
            node.next = current
            if previous.value is None:
                self.head = node
            if node.next is None:
                self.tail = node
            self.size += 1
            return True
        else:
            return False

    def pop(self, index):
        if 0 <= index <= self.size and self.head is not None:
            current = self.head
            previous = Node(next=current)
            count = 0
            while count < index:
                previous = current
                current = current.next
                count += 1
            previous.next = current.next
            if previous.value is None:
                self.head = current.next
            if current.next is None:
                self.tail = previous
            self.size -= 1
            return current.value
        else:
            return None

    def remove(self, item):
        found = False
        current = self.head
        previous = Node(next=current)
        index = 0
        while not found and current is not None:
            if current.value == item:
                found = True
            else:
                previous = current
                current = current.next
            index += 1
        if found:
            previous.next = current.next
            if previous.value is None:
                self.head = current.next
            if current.next is None:
                self.tail = previous
            self.size -= 1
            return index
        else:
            return -1

    def find(self, item):
        current = self.head
        count = 0
        while current is not None:
            if current.value == item:
                return count
            else:
                current = current.next
                count += 1
        return -1
        
    def iter(self):
        current = self.head
        while current is not None:
            yield current.value
            current = current.next

    def size(self):
        return self.size

    def clear(self):
        self.head = None
        self.tail = None
        self.size = 0

    def is_empty(self):
        return self.size == 0
        
    def __len__(self):
        return self.size()

    def __iter__(self):
        iter self.iter()

    def __getitem__(self, index):
        return self.find(index)

    def __contains__(self, item):
        return self.find(item) != -1

JavaScript实现单向链表

// ES6
class Node {
    constructor(value=null, next=null) {
        this.value = value;
        this.next = next;
    }
}

class LinkedList {
    constructor() {
        this.head = null;
        this.tail = null;
        this.size = 0;
    }
    append(value) {
        let node = new Node(value);
        if (this.head === null) {
            this.head = node;
            this.tail = node;
        } else {
            this.tail.next = temp;
            this.tail = temp;
        }
        this.size += 1;
    }
    insert(index, value) {
        if (0 <= index <= this.size) {
            let node = new Node(value);
            let current = this.head;
            let previous = new Node(next=current);
            let count = 0;
            while (count < index) {
                previous = current;
                current = current.next;
                count += 1;
            }
            previous.next = node
            node.next = current
            if (previous.value === null) {
                this.head = node;
            }
            if (node.next === null) {
                this.tail = node;
            }
            this.size += 1
            return true;
        } else {
            return false;
        }
    }
    pop(index) {
        if (0 <= index <= self.size && this.head === null) {
            let current = this.head;
            let previous = new Node(next=current);
            let count = 0;
            while (count < index) {
                previous = current;
                current = current.next;
                count += 1;
            }
            previous.next = current.next;
            if (previous.value === null) {
                this.head = current.next;
            }
            if (current.next === null) {
                this.tail = previous;
            }
            this.size -= 1;
            return current.value;
        } else {
            return null;
        }
    }
    remove(item) {
        let found = false;
        let current = this.head;
        let previous = new Node(next=current);
        let index = 0;
        while (! found && current !== null) {
            if (current.value === item) {
                found = true;
            } else {
                previous = current;
                current = current.next;
            }
            index += 1
        }
        if (found) {
            previous.next = current.next;
            if (previous.value === null) {
                this.head = current.next;
            }
            if (current.next === null) {
                this.tail = previous;
            }
            this.size -= 1;
            return index;
        } else {
            return -1;
        }
    }
    find(item) {
        let current = this.head;
        let count = 0;
        while (current !== null) {
            if (current.value === item) {
                return count;
            } else {
                current = current.next;
                count += 1;
            }
        }
        return -1;
    }
    iter() {
        let current = this.head;
        while (current !== null) {
            yield current.value;
            current = current.next;
        }
    }
    size() {
        return this.size;
    }
    clear() {
        this.head = null;
        this.tail = null;
        this.size = 0;
    }
    isEmpty() {
        return this.size === 0;
    }
}