線性結構數組與鏈表

xi4oh4o 發布于2019-07-31 11:13 / 2049人閱讀

摘要：線性結構數組與鏈表線性結構線性數據結構有兩端，有時被稱為左右，某些情況被稱為前后。將兩個線性數據結構區分開的方法是添加和移除項的方式，特別是添加和移除項的位置。相對于數組，鏈表的好處在于，添加或移除元素的時候不需要移動其他元素。

線性結構數組與鏈表 線性結構

線性數據結構有兩端，有時被稱為左右，某些情況被稱為前后。你也可以稱為頂部和底部，名字都不重要。將兩個線性數據結構區分開的方法是添加和移除項的方式，特別是添加和移除項的位置。例如一些結構允許從一端添加項，另一些允許從另一端移除項。

數組或列表

數組(Array)是編程界最常見的數據結構，有些編程語言被稱作位列表(List)。幾乎所有編程語言都原生內置數組類型，只是形式向略有不同，因為數組是最簡單的內存數據結構。

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

鏈表

數組的缺點：要存儲多個元素，數組(或列表)可能是最常見的數據結構。但是數組不總是組織數據的最佳結構。在大多數編程語言中，數組的大小是固定的，所以當數組被填滿時，再要加入新的元素會非常困難。并且從數組起點或中間插入或移除元素的成本很高，因為需要將數組中的其他元素向前后平移。

鏈表(Linked list)中的元素在內存中不是連續存放的。鏈表是由一組節點(Node)組成的集合，每個節點由元素本身和一個指向下一個元素的引用(也被稱作鏈接或指針)組成。相對于數組，鏈表的好處在于，添加或移除元素的時候不需要移動其他元素。

鏈表的種類

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

雙向鏈表(Doubly linked list)和單向鏈表的區別在于，在鏈表中的節點引用是雙向的，一個指向下一個元素，一個指向上一個元素。

循環鏈表(Circular linked list)和單向鏈表類似，節點類型都一樣。唯一的區別是，鏈表的尾節點引用指向頭節點。

雙向循環鏈表：類似于雙向鏈表，尾節點的后置引用指向頭節點，頭節點的前置引用指向尾節點。

單向鏈表的操作

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

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

云服務器 GPU云服務器具有線性結構的數據結構是線性表的存儲結構鏈表數據結構隊列 linux 數據結構鏈表

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://specialneedsforspecialkids.com/yun/44808.html

線性結構數組與鏈表

摘要：線性結構數組與鏈表線性結構線性數據結構有兩端，有時被稱為左右，某些情況被稱為前后。將兩個線性數據結構區分開的方法是添加和移除項的方式，特別是添加和移除項的位置。相對于數組，鏈表的好處在于，添加或移除元素的時候不需要移動其他元素。線性結構數組與鏈表線性結構線性數據結構有兩端，有時被稱為左右，某些情況被稱為前后。你也可以稱為頂部和底部，名字都不重要。將兩個線性數據結構區分開的方法...

edagarli 2019-08-23 12:22 評論0 收藏0
前言與鏈表實現數組

摘要：數據結構可以分為列表線性樹形圖四種基本結構。即承載數據的形式。數據結構中的線性結構有數組和鏈表，本文即對鏈表進行簡單總結，在后續文章中會實現幾種基本的數據結構。緣起最近工作上需要依照現有數據生成嵌套json對象形式的組織機構列表，一時覺得無從下手，請教同事大神才知道此乃數據結構相關知識，遂惡補相關基礎并在此記錄。數據結構可以分為：1、列表；2、線性；3、樹形；4、圖四種基本...

ingood 2019-08-20 14:02 評論0 收藏0
數據結構與算法：二分查找

摘要：為檢查長度為的列表，二分查找需要執行次操作。最后需要指出的一點是高水平的讀者可研究一下二叉樹關于二叉樹，戳這里數據結構與算法二叉樹算法常見練習在一個二維數組中，每一行都按照從左到右遞增的順序排序，每一列都按照從上到下遞增的順序排序。常見數據結構簡單數據結構（必須理解和掌握）有序數據結構：棧、隊列、鏈表。有序數據結構省空間（儲存空間小）無序數據結構：集合、字典、散列表，無序...

zsirfs 2019-08-23 15:33 評論0 收藏0
數據結構與算法：二分查找

摘要：為檢查長度為的列表，二分查找需要執行次操作。最后需要指出的一點是高水平的讀者可研究一下二叉樹關于二叉樹，戳這里數據結構與算法二叉樹算法常見練習在一個二維數組中，每一行都按照從左到右遞增的順序排序，每一列都按照從上到下遞增的順序排序。常見數據結構簡單數據結構（必須理解和掌握）有序數據結構：棧、隊列、鏈表。有序數據結構省空間（儲存空間小）無序數據結構：集合、字典、散列表，無序...

you_De 2019-08-16 15:26 評論0 收藏0
數據結構與算法：二分查找

摘要：為檢查長度為的列表，二分查找需要執行次操作。最后需要指出的一點是高水平的讀者可研究一下二叉樹關于二叉樹，戳這里數據結構與算法二叉樹算法常見練習在一個二維數組中，每一行都按照從左到右遞增的順序排序，每一列都按照從上到下遞增的順序排序。常見數據結構簡單數據結構（必須理解和掌握）有序數據結構：棧、隊列、鏈表。有序數據結構省空間（儲存空間小）無序數據結構：集合、字典、散列表，無序...

gotham 2019-07-31 10:07 評論0 收藏0