快捷導(dǎo)航

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

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

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

鏈表的概念

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

鏈表的存儲結(jié)構(gòu)特點(diǎn)

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

單鏈表

鏈表通過每個結(jié)點(diǎn)的鏈域?qū)⒕€性表的n個結(jié)點(diǎn)按其邏輯順序鏈接在一起構(gòu)成單鏈表。單鏈表即單向鏈表，單向指的是其指針域所存儲的信息只能為一個方向。具體來說，單鏈表中的每個存儲單元中，除了需要存儲每個單元的數(shù)據(jù)外，還必須附帶儲存其直接后繼存儲單元的地址信息。如圖所示：

單鏈表的一個結(jié)點(diǎn)

單鏈表的結(jié)點(diǎn)

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

結(jié)點(diǎn)的指針域以此指向后繼結(jié)點(diǎn)構(gòu)成了鏈表

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

class ListNode<T>{
    value : T //數(shù)據(jù)域
    next : ListNode<T> | null //指針域

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

單鏈表的基本操作

增加結(jié)點(diǎn)

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

從鏈表左端增加結(jié)點(diǎn)
從鏈表右端增加結(jié)點(diǎn)
從指定位置增加結(jié)點(diǎn)
…
這里我們介紹從鏈表右端增加一個結(jié)點(diǎn)：

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

刪除結(jié)點(diǎn)

刪除結(jié)點(diǎn)是從鏈表中刪除一個結(jié)點(diǎn)，同樣刪除的方法也有很多：

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

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

    }

打印鏈表

打印鏈表很簡單，就是將這個鏈表的每個結(jié)點(diǎn)都遍歷一次并且每遍歷到一個結(jié)點(diǎn)就將這個結(jié)點(diǎn)的數(shù)據(jù)輸出即可

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

鏈表功能測試

增加結(jié)點(diǎn)

增加結(jié)點(diǎn)并打印

測試結(jié)果如下：

增加結(jié)點(diǎn)測試結(jié)果

刪除結(jié)點(diǎn)

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

測試結(jié)果如下：

刪除結(jié)點(diǎn)測試結(jié)果

完整代碼實(shí)現(xiàn)

//鏈表
//定義一個結(jié)點(diǎ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;
    }

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

    //刪除結(jié)點(diǎn)
    remove(value : T){
        const newNode = new ListNode(value);
        let current = this.head;
        if(!current){
            console.log('該結(jié)點(diǎn)不存在,刪除失敗')
        }
        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('該結(jié)點(diǎn)不存在,刪除失敗')
        }

    }

    //打印鏈表
    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();

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

您可能感興趣的文章: