หลังจากเพิ่งจบการศึกษาจาก bootcamp การเข้ารหัสฉันได้ศึกษาโครงสร้างข้อมูลและอัลกอริทึมเพื่อพัฒนาความรู้พื้นฐานให้ดียิ่งขึ้น รายการที่เชื่อมโยงเป็นโครงสร้างข้อมูลที่ค่อนข้างเรียบง่าย แต่เป็นพื้นฐานสำหรับโครงสร้างข้อมูลที่ซับซ้อนมากขึ้นในการก้าวไปข้างหน้า บทความนี้จะกล่าวถึงรายการที่เชื่อมโยง - จุดแข็งจุดอ่อนและวิธีการนำไปใช้

โครงสร้างข้อมูลคือวิธีการจัดระเบียบและเก็บข้อมูลอย่างมีประสิทธิภาพ

โครงสร้างข้อมูลคืออะไร?

โครงสร้างข้อมูลคือวิธีการจัดระเบียบและเก็บข้อมูลอย่างมีประสิทธิภาพ สิ่งเหล่านี้ช่วยให้เราสามารถเก็บข้อมูลไว้เพื่อให้เราสามารถเข้าถึงได้ในภายหลัง - ค้นหารายการเฉพาะหรือจัดเรียงรายการเพื่อให้มีคำสั่งซื้อที่แน่นอนหรือแม้กระทั่งการจัดการชุดข้อมูลขนาดใหญ่ JavaScript มีโครงสร้างข้อมูลที่คุณน่าจะคุ้นเคยเป็นอย่างดี - อาร์เรย์และวัตถุ สิ่งเหล่านี้เป็นโครงสร้างข้อมูลดั้งเดิมที่มีพื้นฐานมาจากภาษา Non-primitive data Structure คือโครงสร้างข้อมูลที่ถูกกำหนดโดยโปรแกรมเมอร์ ตัวอย่าง ได้แก่ สแต็กคิวต้นไม้กราฟและตารางแฮช

รายการที่เชื่อมโยงคืออะไร?

รายการที่เชื่อมโยงคือโครงสร้างข้อมูลเชิงเส้นที่เก็บองค์ประกอบตามลำดับ เสียงคุ้นเคย? พวกมันคล้ายกับอาร์เรย์ แต่ไม่เหมือนกันซะทีเดียว อาร์เรย์มีการจัดทำดัชนีเป็นศูนย์ซึ่งหมายความว่าดัชนีแต่ละตัวจะถูกจับคู่กับค่าและองค์ประกอบแรกของอาร์เรย์เริ่มต้นที่ดัชนี 0 คุณสามารถดึงองค์ประกอบจากอาร์เรย์ได้อย่างง่ายดายตราบใดที่คุณรู้จักดัชนี

ในทางกลับกันรายการที่เชื่อมโยงประกอบด้วยโหนดที่ชี้ไปยังโหนดอื่น ๆ แต่ละโหนดรู้จักตัวเองและโหนดถัดไปเท่านั้น ในฐานะโครงสร้างข้อมูลเชิงเส้นรายการต่างๆจะถูกจัดเรียงตามลำดับ คุณอาจคิดว่ามันเป็นรถไฟ - รถรางแต่ละคันเชื่อมต่อกับรถรางคันถัดไปและอื่น ๆ รายการที่เชื่อมโยงจะไม่ถูกจัดทำดัชนีดังนั้นคุณจึงไม่สามารถเข้าถึงองค์ประกอบที่ 5 ได้โดยตรง คุณต้องเริ่มต้นที่จุดเริ่มต้นไปที่ถัดไปและไปที่ถัดไปจนกว่าคุณจะพบองค์ประกอบที่ 5 โหนดแรกเรียกว่าส่วนหัวและโหนดสุดท้ายเรียกว่าหาง รายการที่เชื่อมโยงมีหลายประเภท ได้แก่ รายการที่เชื่อมโยงแบบเดี่ยวรายการที่เชื่อมโยงแบบทวีคูณและรายการที่เชื่อมโยงแบบวงกลม เพื่อประโยชน์ของบทความนี้ฉันจะเน้นไปที่รายการที่เชื่อมโยงกัน

การเข้าถึงองค์ประกอบทั่วทั้งอาร์เรย์นั้นง่ายกว่า แต่ต้องเสียค่าใช้จ่าย

เหตุใดจึงต้องใช้รายการที่เชื่อมโยงกับอาร์เรย์

คุณอาจสงสัย - แต่ทำไมต้องใช้สิ่งนี้ถ้าฉันสามารถเข้าถึงองค์ประกอบโดยตรงด้วยอาร์เรย์ นี่คือเรื่องจริง! การเข้าถึงองค์ประกอบทั่วทั้งอาร์เรย์นั้นง่ายกว่า แต่ต้องเสียค่าใช้จ่าย

อาร์เรย์จะถูกจัดทำดัชนี - ดังนั้นเมื่อใดก็ตามที่คุณต้องการลบองค์ประกอบจากจุดเริ่มต้นหรือตรงกลางดัชนีทั้งหมดต่อไปนี้จะต้องถูกเลื่อนออกไป สิ่งนี้เป็นจริงเช่นกันหากคุณต้องการแทรกองค์ประกอบ - องค์ประกอบต่อไปนี้ทั้งหมดต้องได้รับการจัดทำดัชนีใหม่ เมื่อใส่หรือถอดองค์ประกอบจากรายการที่เชื่อมโยงคุณไม่จำเป็นต้อง Reindex - ทั้งหมดมันใส่ใจเกี่ยวกับการเป็นโหนดจะชี้ไปที่

การใช้รายการที่เชื่อมโยงเดี่ยว

มีรายการที่เชื่อมโยงหลายประเภท - เดี่ยวทวีคูณและวงกลม รายการที่เชื่อมโยงเดี่ยวเป็นรายการที่เชื่อมโยงโดยแต่ละโหนดมีค่าและตัวชี้ไปยังโหนดถัดไป (null ถ้าเป็นโหนดหาง) ในทางกลับกันรายการที่เชื่อมโยงแบบทวีคูณมีตัวชี้เพิ่มเติมไปยังโหนดก่อนหน้า รายการที่เชื่อมโยงแบบวงกลมคือจุดที่โหนดหางชี้กลับไปที่โหนดส่วนหัว

หมายเหตุ: หากคุณเป็นผู้เรียนด้วยภาพVisuAlgoเป็นสถานที่ที่ดีเยี่ยมในการเล่นและดูโครงสร้างข้อมูลผ่านการเปลี่ยนแปลง

หากคุณต้องการข้ามไปข้างหน้าสำหรับรหัสที่สมบูรณ์: ตรวจสอบข้อมูลสำคัญของ GitHubนี้

การสร้างโหนด

เริ่มต้นด้วยการสร้างโหนดเพื่อใช้งาน จะมีค่าและตัวชี้ถัดไปซึ่งจะระบุเพื่อนบ้านที่ตามมา

class Node {    
    constructor(val) {        
        this.val = val;        
        this.next = null;    
    }
}

เราจะเริ่มต้นด้วยการสร้างคลาสที่เรียกว่า SinglyLinkedList และให้พื้นฐานสำหรับหัวหางและความยาวของรายการ

class SinglyLinkedList {    
      constructor() {        
          this.head = null;
          this.tail = null;
          this.length = 0;
      }
}

สำหรับการเพิ่มโหนดต่อท้ายเราจะตรวจสอบว่ามีหัวที่ประกาศอยู่ในรายการหรือไม่ ถ้าไม่ให้ตั้งค่าส่วนหัวและส่วนท้ายเป็นโหนดที่สร้างขึ้นใหม่ หากมีคุณสมบัติ head อยู่แล้วให้ตั้งค่าคุณสมบัติถัดไปบน tail เป็นโหนดใหม่และคุณสมบัติ tail เป็นโหนดใหม่ เราจะเพิ่มความยาวทีละ 1

push(val) {
        var newNode = new Node(val)
        if (!this.head) {
            this.head = newNode
            this.tail = newNode
        } else {
            this.tail.next = newNode
            this.tail = newNode
        }
        this.length++;
        return this;
}

สำหรับการลบโหนดในตอนท้ายเราต้องตรวจสอบก่อนว่ามีโหนดในรายการหรือไม่ หากมีโหนดเราจะต้องวนรอบรายการจนกว่าเราจะไปถึงหาง เราจะตั้งค่าคุณสมบัติถัดไปของโหนดที่สองเป็นโหนดสุดท้ายให้เป็นโมฆะตั้งค่าคุณสมบัติหางเป็นโหนดนั้นลดความยาวลง 1 และส่งคืนค่าของโหนดที่ถูกลบออก

pop() {
        if (!this.head) return undefined;
        var current = this.head
        var newTail = current
        while (current.next) {
            newTail = current
            current = current.next;
        }
        this.tail = newTail;
        this.tail.next = null;
        this.length--;
        if (this.length === 0) {
            this.head = null;
            this.tail = null;
        }
        return current;
}

ในการลบโหนดออกจากจุดเริ่มต้นเราตรวจสอบว่ามีโหนดในรายการหรือไม่ เราจะเก็บคุณสมบัติ head ปัจจุบันไว้ในตัวแปรและตั้งค่า head ให้เป็นโหนดถัดไปของ head ปัจจุบัน ลดความยาวลง 1 และส่งคืนค่าของโหนดที่ลบออก

shift() {
        if (!this.head) return undefined
        var oldHead = this.head;
        this.head = oldHead.next;
        this.length--
        if (this.length===0) {
            this.head = null;
            this.tail = null;
        }
        return oldHead
}

ในการเพิ่มโหนดไปยังจุดเริ่มต้นขั้นแรกให้สร้างโหนดและตรวจสอบว่ามีคุณสมบัติส่วนหัวในรายการหรือไม่ ถ้าเป็นเช่นนั้นให้ตั้งค่าคุณสมบัติถัดไปของโหนดที่สร้างขึ้นใหม่เป็นส่วนหัวปัจจุบันตั้งค่าส่วนหัวเป็นโหนดใหม่และเพิ่มความยาว

unshift(val) {
        var newNode = new Node(val)
        if (!this.head) {
            this.head = newNode;
            this.tail = newNode;
        } else {
            newNode.next = this.head;
            this.head = newNode;
        }
        this.length++
        return this
}

ในการเข้าถึงโหนดตามตำแหน่งในรายการก่อนอื่นเราจะตรวจสอบว่าดัชนีนั้นเป็นดัชนีที่ถูกต้องหรือไม่ หลังจากนั้นเราจะวนซ้ำรายการในขณะที่เก็บตัวแปรตัวนับ เมื่อตัวแปรตัวนับตรงกับดัชนีเราจะส่งคืนโหนดที่พบ

get(idx) {
        if (idx < 0 || idx >= this.length) return null
        var counter = 0;
        var current = this.head
        while (counter !== idx) {
            current = current.next;
            counter++;
        }
        return current;
}

ในการเปลี่ยนโหนดตามตำแหน่งอันดับแรกเราจะหาโหนดโดยใช้เมธอด get และตั้งค่าเป็นค่าใหม่

set(idx, val) {
        var foundNode = this.get(idx)
        if (foundNode) {
            foundNode.val = val
            return true;
        }
        return false;
}

ในการแทรกโหนดเราต้องตรวจสอบดัชนีก่อน ถ้ามันเท่ากับ 0 เราใช้วิธี unshift ถ้ามันเท่ากับความยาวเราก็ดันเข้าไปในรายการ มิฉะนั้นเราจะได้รับโหนดก่อนโดยใช้เมธอด get ที่หนึ่งน้อยกว่าดัชนี โดยพื้นฐานแล้วเราต้องติดตามโหนดก่อนและหลังดัชนีที่เลือกเพื่อให้แน่ใจว่าพอยน์เตอร์ของเราถูกนำไปยังโหนดที่ถูกต้อง

insert(idx, val) {
        if (idx < 0 || idx > this.length) return false;
        if (idx === 0) {
            this.unshift(val)
            return true;
        };
        if (idx === this.length) {
            this.push(val);
            return true;
        };
        var newNode = new Node(val);
        var beforeNode = this.get(idx-1);
        var afterNode = beforeNode.next;
        beforeNode.next = newNode;
        newNode.next = afterNode;
        this.length++;
        return true;
}

ในการลบโหนดตามตำแหน่งเราจะใช้เมธอด get ของเราอีกครั้งและใช้หลักการเดียวกับที่เราใช้ในการแทรกโหนด ด้วยการติดตามโหนดก่อนหน้าดัชนีที่เลือกเราสามารถจัดทำพอยน์เตอร์ของเราได้

remove(idx) {
        if (idx < 0 || idx > this.length) return undefined;
        if (idx === this.length-1) {
            this.pop()
        }
        if (idx === 0) {
            this.shift()
        }
        var prevNode = this.get(idx-1)
        var removeNode = prevNode.next
        prevNode.next = removeNode.next
        this.length--;
        return removeNode;
}

จุดแข็งของรายการที่เชื่อมโยง

ประโยชน์ของการใช้รายการที่เชื่อมโยงคือความสามารถในการแทรกและลบองค์ประกอบอย่างรวดเร็ว เนื่องจากไม่ได้จัดทำดัชนีรายการที่เชื่อมโยงการแทรกองค์ประกอบจึงค่อนข้างรวดเร็วและง่ายดาย

การเพิ่มที่ส่วนท้ายของรายการที่เชื่อมโยงเพียงแค่ต้องการให้หางเก่าชี้ไปที่โหนดใหม่และคุณสมบัติหางจะถูกตั้งค่าเป็นโหนดใหม่ การเพิ่มไปที่จุดเริ่มต้นของรายการที่เชื่อมโยงเป็นหลักฐานเดียวกัน แต่โหนดใหม่ชี้ไปที่ส่วนหัวเก่าและคุณสมบัติส่วนหัวจะถูกตั้งค่าเป็นโหนดใหม่ การกระทำที่เหมือนกันโดยพื้นฐานดังนั้นการแทรกจึงเป็น O (1)

หมายเหตุ: การแทรกกลางรายการที่เชื่อมโยงต้องใช้การค้นหาเพื่อค้นหาโหนดของคุณ (O (N)) จากนั้นจึงแทรกโหนด (O (1))

การลบโหนดออกจากรายการที่เชื่อมโยงอาจเป็นเรื่องง่าย ... แต่ก็ไม่เช่นกัน ขึ้นอยู่กับว่าที่ไหน การลบโหนดออกจากจุดเริ่มต้นของรายการทำได้ง่าย - โหนดที่สองกลายเป็นส่วนหัวใหม่และเราตั้งค่าตัวชี้ถัดไปของส่วนหัวเก่าเป็นโมฆะ การลบออกจากจุดสิ้นสุดนั้นยุ่งยากกว่าเนื่องจากต้องผ่านรายการทั้งหมดและหยุดที่โหนดที่สองถึงโหนดสุดท้าย กรณีที่เลวร้ายที่สุด O (N) และกรณีที่ดีที่สุด O (1)

จุดอ่อนของรายการที่เชื่อมโยง

จุดอ่อนของรายการที่เชื่อมโยงเกิดจากการขาดการจัดทำดัชนีใหม่ เนื่องจากคุณไม่สามารถเข้าถึงองค์ประกอบได้โดยตรงจึงทำให้ค้นหาและเข้าถึงองค์ประกอบได้ยากขึ้น

การค้นหาและการเข้าถึงโหนดในรายการที่เชื่อมโยงจำเป็นต้องเริ่มต้นที่จุดเริ่มต้นของรายการและติดตามเส้นทางของ breadcrumbs ในรายการ หากเรากำลังค้นหาโหนดในตอนท้ายของรายการเราจะต้องผ่านรายการที่เชื่อมโยงทั้งหมดทำให้มีความซับซ้อนของเวลา O (N) อย่างมีประสิทธิภาพ เมื่อรายการเติบโตขึ้นจำนวนการดำเนินงานก็เพิ่มขึ้น เมื่อเทียบกับอาร์เรย์ที่มีการเข้าถึงแบบสุ่มต้องใช้เวลาคงที่ในการเข้าถึงองค์ประกอบ

แค่นั้นแหละ!

รายการที่เชื่อมโยงเป็นทางเลือกที่ดีสำหรับอาร์เรย์เมื่อการแทรกและการลบที่จุดเริ่มต้นเป็นการดำเนินการหลัก อาร์เรย์จะถูกจัดทำดัชนีในขณะที่ไม่มีรายการที่เชื่อมโยง รายการที่เชื่อมโยงยังเป็นโครงสร้างข้อมูลพื้นฐานที่สแต็กและคิวสร้างขึ้นซึ่งฉันจะพูดถึงในบทความต่อไป ถ้าคุณทำมันมาตลอดทางขอชื่นชมคุณและฉันหวังว่าคุณจะได้เรียนรู้นักเก็ตตัวน้อยไปพร้อมกับเส้นทางการเขียนโปรแกรมของคุณ!

อ้างอิง

โครงสร้างข้อมูลใน JavaScript รายการที่เชื่อมโยงคืออะไร? [ส่วนที่ 1]