線性結(jié)構(gòu) 數(shù)組與鏈表

xi4oh4o 發(fā)布于2019-07-31 11:13 / 2097人閱讀

摘要：線性結(jié)構(gòu)數(shù)組與鏈表線性結(jié)構(gòu)線性數(shù)據(jù)結(jié)構(gòu)有兩端，有時(shí)被稱為左右，某些情況被稱為前后。將兩個(gè)線性數(shù)據(jù)結(jié)構(gòu)區(qū)分開的方法是添加和移除項(xiàng)的方式，特別是添加和移除項(xiàng)的位置。相對(duì)于數(shù)組，鏈表的好處在于，添加或移除元素的時(shí)候不需要移動(dòng)其他元素。

線性結(jié)構(gòu) 數(shù)組與鏈表 線性結(jié)構(gòu)

線性數(shù)據(jù)結(jié)構(gòu)有兩端，有時(shí)被稱為左右，某些情況被稱為前后。你也可以稱為頂部和底部，名字都不重要。將兩個(gè)線性數(shù)據(jù)結(jié)構(gòu)區(qū)分開的方法是添加和移除項(xiàng)的方式，特別是添加和移除項(xiàng)的位置。例如一些結(jié)構(gòu)允許從一端添加項(xiàng)，另一些允許從另一端移除項(xiàng)。

數(shù)組或列表

數(shù)組(Array)是編程界最常見的數(shù)據(jù)結(jié)構(gòu)，有些編程語言被稱作位列表(List)。幾乎所有編程語言都原生內(nèi)置數(shù)組類型，只是形式向略有不同，因?yàn)閿?shù)組是最簡單的內(nèi)存數(shù)據(jù)結(jié)構(gòu)。

數(shù)組的定義是：一個(gè)存儲(chǔ)元素的線性集合(Collection)，元素可以通過索引(Index)來任意存取，索引通常是數(shù)字，用來計(jì)算元素之間存儲(chǔ)位置的偏移量。

鏈表

數(shù)組的缺點(diǎn)：要存儲(chǔ)多個(gè)元素，數(shù)組(或列表)可能是最常見的數(shù)據(jù)結(jié)構(gòu)。但是數(shù)組不總是組織數(shù)據(jù)的最佳結(jié)構(gòu)。在大多數(shù)編程語言中，數(shù)組的大小是固定的，所以當(dāng)數(shù)組被填滿時(shí)，再要加入新的元素會(huì)非常困難。并且從數(shù)組起點(diǎn)或中間插入或移除元素的成本很高，因?yàn)樾枰獙?shù)組中的其他元素向前后平移。

鏈表(Linked list)中的元素在內(nèi)存中不是連續(xù)存放的。鏈表是由一組節(jié)點(diǎn)(Node)組成的集合，每個(gè)節(jié)點(diǎn)由元素本身和一個(gè)指向下一個(gè)元素的引用(也被稱作鏈接或指針)組成。相對(duì)于數(shù)組，鏈表的好處在于，添加或移除元素的時(shí)候不需要移動(dòng)其他元素。

鏈表的種類

單向鏈表(Singly linked list)：是最基本的鏈表，每個(gè)節(jié)點(diǎn)一個(gè)引用，指向下一個(gè)節(jié)點(diǎn)。單向鏈表的第一個(gè)節(jié)點(diǎn)稱為頭節(jié)點(diǎn)(head node)，最后一個(gè)節(jié)點(diǎn)稱為尾節(jié)點(diǎn)(tail node)，尾節(jié)點(diǎn)的引用為空（None），不指向下一個(gè)節(jié)點(diǎn)。

雙向鏈表(Doubly linked list)和單向鏈表的區(qū)別在于，在鏈表中的節(jié)點(diǎn)引用是雙向的，一個(gè)指向下一個(gè)元素，一個(gè)指向上一個(gè)元素。

循環(huán)鏈表(Circular linked list)和單向鏈表類似，節(jié)點(diǎn)類型都一樣。唯一的區(qū)別是，鏈表的尾節(jié)點(diǎn)引用指向頭節(jié)點(diǎn)。

雙向循環(huán)鏈表：類似于雙向鏈表，尾節(jié)點(diǎn)的后置引用指向頭節(jié)點(diǎn)，頭節(jié)點(diǎn)的前置引用指向尾節(jié)點(diǎn)。

單向鏈表的操作

方法	操作
append	向鏈表尾部添加一個(gè)元素
insert	在鏈表的指定位置插入一個(gè)元素
pop	從鏈表特定位置刪除并返回元素
remove	從鏈表中刪除給定的元素
find	返回元素的索引
iter	迭代鏈表元素
size	獲取鏈表大小
clear	清空鏈表

Python實(shí)現(xiàn)單向鏈表

# 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實(shí)現(xiàn)單向鏈表

// 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;
    }
}

云服務(wù)器 GPU云服務(wù)器具有線性結(jié)構(gòu)的數(shù)據(jù)結(jié)構(gòu)是線性表的存儲(chǔ)結(jié)構(gòu) 鏈表數(shù)據(jù)結(jié)構(gòu)隊(duì)列 linux 數(shù)據(jù)結(jié)構(gòu) 鏈表

文章版權(quán)歸作者所有，未經(jīng)允許請(qǐng)勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。

轉(zhuǎn)載請(qǐng)注明本文地址：http://m.hztianpu.com/yun/44808.html