TypeScript實現(xiàn)單鏈表的示例代碼

更新時間：2024年08月23日 11:27:38 作者：samroom

鏈表是一種物理存儲單元上非連續(xù)、非順序的存儲結構,本文主要介紹了TypeScript實現(xiàn)單鏈表的示例代碼,文中通過示例代碼介紹的非常詳細,對大家的學習或者工作具有一定的參考學習價值,需要的朋友們下面隨著小編來一起學習學習吧

鏈表的概念

鏈表是一種物理存儲單元上非連續(xù)、非順序的存儲結構，它由一系列結點組成，其特點在于結點可以在運行時動態(tài)生成。

鏈表的存儲結構特點

鏈表的每個結點包括兩個部分：
- 一個是存儲數據元素的數據域
- 另一個存儲下一個結點地址的指針域
鏈表可以用任意一組存儲單元來存儲其中的數據結構，與數組不同的是它的存儲單元可以是不連續(xù)的。

單鏈表

鏈表通過每個結點的鏈域將線性表的n個結點按其邏輯順序鏈接在一起構成單鏈表。單鏈表即單向鏈表，單向指的是其指針域所存儲的信息只能為一個方向。具體來說，單鏈表中的每個存儲單元中，除了需要存儲每個單元的數據外，還必須附帶儲存其直接后繼存儲單元的地址信息。如圖所示：

單鏈表的一個結點

單鏈表的結點

鏈表是由一個一個節(jié)點通過某種關系建立關聯(lián)構成的一種數據結構，單鏈表也是如此。單鏈表中的所有節(jié)點只有一個指向各自直接后繼節(jié)點的指針域以及各自的數據域：

結點的指針域以此指向后繼結點構成了鏈表

由于在TypeScript中沒有指針類型，所以我們需要用一個類來模擬一個結點：
由于在Typescript中泛型可以提高我們代碼的可復用性和靈活性，所以下面在定義結點和創(chuàng)建鏈表時會用到泛型。

class ListNode<T>{
    value : T //數據域
    next : ListNode<T> | null //指針域

    constructor(value: T){
        this.value = value;
        this.next = null
    }
}

單鏈表的基本操作

增加結點

增加結點是指為單鏈表增添節(jié)點，增加元素的方法有很多：

從鏈表左端增加結點
從鏈表右端增加結點
從指定位置增加結點
…
這里我們介紹從鏈表右端增加一個結點：

 //添加結點
    add(value:T){
        const newNode = new ListNode(value); //首先需要創(chuàng)建一個新結點
        //頭結點為空，那么這個新結點就是鏈表的頭結點
        if(!this.head){
            this.head=newNode;
        }
        //頭結點非空
        else{
            let current = this.head;
            //遍歷鏈表，直到找到鏈表的末尾
            while(current.next)
            {
                current = current.next
            }
            current.next = newNode;//將鏈表的最后一個節(jié)點的指針域指向新創(chuàng)建的結點
        }
    }

刪除結點

刪除結點是從鏈表中刪除一個結點，同樣刪除的方法也有很多：

按照結點的索引號刪除鏈表中的單個結點
按照索引號刪除鏈表中某個節(jié)點及其之后的結點
給定兩個索引號a,b,刪除[a,b]的一段結點
…
這里我們介紹刪除指定數據所在的結點：

 remove(value : T){
        const newNode = new ListNode(value);
        let current = this.head;
        if(!current){
            console.log('該結點不存在,刪除失敗')
        }
        //刪除的結點是頭結點
        else if(current && current.value == value){
            this.head = current.next;
            console.log('刪除成功');
        }
        else{
            while(current.next){
                if(current.next.value==value){
                	//讓所要刪除結點的上一個結點的指針域
                	//直接指向所要刪除結點的下一個結點即可
                    current.next = current.next.next;
                    console.log('刪除成功');
                    return;
                }
                current = current.next;
            }
            console.log('該結點不存在,刪除失敗')
        }

    }

打印鏈表

打印鏈表很簡單，就是將這個鏈表的每個結點都遍歷一次并且每遍歷到一個結點就將這個結點的數據輸出即可

 //打印鏈表
    print(){
        let current = this.head;
        while(current){
            console.log(current);
            current = current.next
        }
    }

鏈表功能測試

增加結點

增加結點并打印

測試結果如下：

增加結點測試結果

刪除結點

創(chuàng)建鏈表并刪除其中的‘hello'元素

測試結果如下：

刪除結點測試結果

完整代碼實現(xiàn)

//鏈表
//定義一個結點類：
class ListNode<T>{
    value : T
    next : ListNode<T> | null

    constructor(value: T){
        this.value = value;
        this.next = null
    }
}

//定義一個鏈表類
class LinkList<T>{
    head:null | ListNode<T>

    constructor(){
        this.head = null;
    }

    //定義方法
    //添加結點
    add(value:T){
        const newNode = new ListNode(value);
        //頭結點為空
        if(!this.head){
            this.head=newNode;
        }
        //頭結點非空
        else{
            let current = this.head;
            while(current.next)
            {
                current = current.next
            }
            current.next = newNode;
        }
    }

    //刪除結點
    remove(value : T){
        const newNode = new ListNode(value);
        let current = this.head;
        if(!current){
            console.log('該結點不存在,刪除失敗')
        }
        else if(current && current.value == value){
            this.head = current.next;
            console.log('刪除成功');
        }
        else{
            while(current.next){
                if(current.next.value==value){
                    current.next = current.next.next;
                    console.log('刪除成功');
                    return;
                }
                current = current.next;
            }
            console.log('該結點不存在,刪除失敗')
        }

    }

    //打印鏈表
    print(){
        let current = this.head;
        while(current){
            console.log(current);
            current = current.next
        }
    }
}

let list = new LinkList()

list.add(10);
list.add('hello');
list.add(true);
list.print();
list.remove('hello');
list.print();

到此這篇關于TypeScript實現(xiàn)單鏈表的示例代碼的文章就介紹到這了,更多相關TypeScript 單鏈表內容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關文章希望大家以后多多支持腳本之家！

您可能感興趣的文章: