پیاده سازی لیست پیوندی در Go

Summarize this content to 400 words in Persian Lang
سلام انجمن DEV.to!

این بخشی از مجموعه ساختارهای داده و الگوریتم های من است. در این مقاله، ما یک لیست لینک شده را پیاده سازی می کنیم، سپس در مقالات بعدی از این مجموعه، انواع دیگر لیست های پیوندی را نیز با استفاده از Go پیاده سازی می کنم.

منبع تصویر: GeeksforGeeks

برای پیاده سازی یک لیست پیوندی منفرد، به ساختارها، یک گره و یک لیست پیوندی منفرد نیاز داریم. اما قبل از شروع به کدنویسی در اینجا نحوه سازماندهی کد خود را دوست دارم:

project
├── singly_linked_list
│ ├── node.go
│ └── list.go
└── main.go

وارد حالت تمام صفحه شوید

از حالت تمام صفحه خارج شوید

یک گره فقط داده ها و یک اشاره گر به گره بعدی را در ساده ترین شکل خود نگه می دارد. بنابراین در اینجا ساختاری است که ما می خواهیم به عنوان یک گره استفاده کنیم (در node.go فایل):

type SinglyNode struct {
data interface{}
next *SinglyNode
}

وارد حالت تمام صفحه شوید

از حالت تمام صفحه خارج شوید

در حال استفاده هستیم interface{} به عنوان نوع داده برای data در ساختار، بنابراین می توانیم هر داده ای را که می خواهیم در داخل گره ذخیره کنیم.

سپس باید چند روش برای استفاده از ساختار گره ای که به تازگی ایجاد کرده ایم تعریف کنیم.

func NewSinglyNode(data interface{}) *SinglyNode {
return &SinglyNode{data: data}
}

وارد حالت تمام صفحه شوید

از حالت تمام صفحه خارج شوید

اگر به زبان های شی گرا عادت دارید، احتمالاً با سازنده چیست آشنا هستید. از آنجایی که Go یک زبان شی گرا نیست، هیچ کلاسی وجود ندارد، اما طبق برخی قراردادها در سراسر جهان Go، ما معمولاً یک تابع با پیشوند کلمه ایجاد می کنیم. New. اما به خاطر داشته باشید که در زبان های OOP new یک کلمه کلیدی خاص است که به معنای ایجاد یک شی است. اینجا New فقط یک پیشوند نام است و دیگر هیچ.

را NewSinglyNode تابع فقط یک آرگومان فراخوانی دریافت می کند data با interface{} تایپ کنید و یک اشاره گر از SinglyNode.

در مرحله بعد، چند دریافت کننده و تنظیم کننده برای گره تعریف می کنیم:

func (n *SinglyNode) SetData(data interface{}) {
n.data = data
}

func (n *SinglyNode) SetNext(next *SinglyNode) {
n.next = next
}

func (n *SinglyNode) GetData() interface{} {
return n.data
}

func (n *SinglyNode) GetNext() (*SinglyNode, error) {
if n.next == nil {
return nil, errors.New(“no next node”)
}
return n.next, nil
}

وارد حالت تمام صفحه شوید

از حالت تمام صفحه خارج شوید

را SetData، Setnext و GetData تا حد زیادی خود توضیحی هستند. را GetNext دو مقدار، یک اشاره گر به بعدی را برمی گرداند SinglyNode و اگر گره بعدی وجود نداشته باشد خطا می دهد.

در اینجا یک تابع اضافی وجود دارد که همیشه دوست دارم اضافه کنم تا همیشه بتوانم بدانم نمایش رشته ساختار من چگونه است:

func (n *SinglyNode) ToString() string {
return n.data.(string)
}

وارد حالت تمام صفحه شوید

از حالت تمام صفحه خارج شوید

اکنون که کار با گره خود تمام شد، باید خود لیست را پیاده سازی کنیم. یک لیست پیوندی مجرد، اولین گره را به عنوان نگه می دارد head و در مورد ترجیح من دو داده دیگر نامیده می شود last آخرین گره را نگه می دارد و a country ویژگی که تعداد گره های اضافه شده به لیست را نگه می دارد.

بنابراین در اینجا اولین خطوط از list.go فایل:

type SinglyLinkedList struct {
head *SinglyNode
last *SinglyNode
count int
}

وارد حالت تمام صفحه شوید

از حالت تمام صفحه خارج شوید

و بدیهی است که یک تابع سازنده مانند برای ایجاد a SinglyLinkedList با سهولت:

func NewSinglyLinkedList() *SinglyLinkedList {
return &SinglyLinkedList{}
}

وارد حالت تمام صفحه شوید

از حالت تمام صفحه خارج شوید

مهمترین تابع در لیست پیوندی، تابعی است که یک گره اضافه می کند. در اینجا اجرای من از چنین عملکردی است:

func (l *SinglyLinkedList) AttachNode(node *SinglyNode) {
if l.head == nil {
l.head = node
} else {
l.last.SetNext(node)
}
l.last = node
l.count++
}

وارد حالت تمام صفحه شوید

از حالت تمام صفحه خارج شوید

تابع به صورت زیر عمل می کند:

بررسی کنید که آیا سر لیست پیوند شده خالی است، در این صورت گره دریافتی را به عنوان سر لیست تنظیم کنید.
اگر هد خالی نباشد، گره دریافتی را به عنوان یک تنظیم می کند next ویژگی آخرین گره
صرف نظر از آنچه قبلاً اتفاق افتاده است، گره فعلی باید آخرین گره باشد، بنابراین دفعه بعد که یک گره اضافه می شود، می تواند به عنوان گره بعدی برای آخرین گره در لیست ما تنظیم شود.
تعداد را یک عدد افزایش دهید.

در اینجا یک تابع است که داده ها را دریافت می کند و یک گره ایجاد می کند و آن را به آن ارسال می کند AttachNode تابع:

func (l *SinglyLinkedList) Add(data interface{}) {
l.AttachNode(NewSinglyNode(data))
}

وارد حالت تمام صفحه شوید

از حالت تمام صفحه خارج شوید

اگرچه این تابع ممکن است اضافی به نظر برسد، اما اضافه کردن گره ها به لیست را بدون ایجاد دستی هر بار آسان می کند.

تابعی برای دریافت ویژگی count نیز:

func (l *SinglyLinkedList) Count() int {
return l.count
}

وارد حالت تمام صفحه شوید

از حالت تمام صفحه خارج شوید

آخرین تابع مورد نیاز تابعی است که باید گره بعدی را در لیست پیوند شده برگرداند:

func (l *SinglyLinkedList) GetNext() (*SinglyNode, error) {
if l.head == nil {
return nil, errors.New(“list is empty”)
}
return l.head, nil
}

وارد حالت تمام صفحه شوید

از حالت تمام صفحه خارج شوید

من ترجیح می دهم این تابع را همان نام گذاری کنم GetNext تابع تعریف شده برای گره ها این کار انجام می شود تا هماهنگی بیشتری وجود داشته باشد. هنگامی که برای اولین بار به یک لیست پیوندی دسترسی پیدا می کنید، نوع آن یک لیست پیوندی است، بنابراین هیچ دسترسی به توابع تعریف شده برای گره ها وجود ندارد. تعریف تابعی با همین نام باعث می شود که بتوانید از آن استفاده کنید GetNext تا آنجا که می خواهید لیست خود را طی کنید.

یک تابع اضافی که من همیشه تمایل به اضافه کردن آن دارم، تابعی برای بازیابی یک گره توسط شاخص است:

func (l *SinglyLinkedList) GetByIndex(index int) (*SinglyNode, error) {
if l.head == nil {
return nil, errors.New(“list is empty”)
}
if index+1 > l.count {
return nil, errors.New(“index out of range”)
}
node, _ := l.GetNext()
for i := 0; i < index; i++ {
node, _ = node.GetNext()
}
return node, nil
}

وارد حالت تمام صفحه شوید

از حالت تمام صفحه خارج شوید

این تابع به صورت زیر عمل می کند:

بررسی کنید که آیا هد خالی است تا خطا را برگردانید
بررسی کنید اگر index+1 بیشتر از تعداد لیست برای بازگشت خطا است. بررسی می کنیم index+1 و نه برای index از آنجایی که ما شاخص هایی را که از 0 شروع می شوند مانند آرایه ها در نظر می گیریم.
اختصاص دهید l.GetNext() به متغیری به نام گره (با نادیده گرفتن خطای با _) سپس برای یک حلقه کمتر از شاخص ارائه شده حلقه کنید زیرا ما قبلاً اولین مورد را در آن ذخیره کرده ایم node متغیر، گره بعدی گره فعلی را به عنوان node دوباره
گره پیموده شده را بدون خطا برگردانید.

اکنون که لیست پیوندی و تعاریف گره خود را داریم، می‌توانیم آن را در ما آزمایش کنیم main.go مانند زیر فایل کنید:

func main() {
list := singly_linked_list.NewSinglyLinkedList()

list.Add(“One”)
list.Add(“Two”)
list.Add(“Three”)

firstNode, err := list.GetNext()
if err != nil {
panic(err)
}

secondNode, err := firstNode.GetNext()
if err != nil {
panic(err)
}

thirdNode, err := secondNode.GetNext()
if err != nil {
panic(err)
}

println(firstNode.ToString()) // One
println(secondNode.ToString()) // Two
println(thirdNode.ToString()) // Three
}

وارد حالت تمام صفحه شوید

از حالت تمام صفحه خارج شوید

یا با استفاده از GetByIndex تابع:

func main() {
list := singly_linked_list.NewSinglyLinkedList()

list.Add(“One”)
list.Add(“Two”)
list.Add(“Three”)

node, err := list.GetByIndex(2)
if err != nil {
panic(err)
}

fmt.Println(node.ToString()) // Three
}

وارد حالت تمام صفحه شوید

از حالت تمام صفحه خارج شوید

BTW! کتاب الکترونیکی رایگان Node.js Essentials من را اینجا ببینید:

در صورت داشتن هرگونه سوال یا پیشنهاد با من تماس بگیرید.

project
├── singly_linked_list
│   ├── node.go
│   └── list.go
└── main.go

type SinglyNode struct {
    data interface{}
    next *SinglyNode
}

func NewSinglyNode(data interface{}) *SinglyNode {
    return &SinglyNode{data: data}
}

func (n *SinglyNode) SetData(data interface{}) {
    n.data = data
}

func (n *SinglyNode) SetNext(next *SinglyNode) {
    n.next = next
}

func (n *SinglyNode) GetData() interface{} {
    return n.data
}

func (n *SinglyNode) GetNext() (*SinglyNode, error) {
    if n.next == nil {
        return nil, errors.New("no next node")
    }
    return n.next, nil
}

func (n *SinglyNode) ToString() string {
    return n.data.(string)
}

type SinglyLinkedList struct {
    head  *SinglyNode
    last  *SinglyNode
    count int
}

func NewSinglyLinkedList() *SinglyLinkedList {
    return &SinglyLinkedList{}
}

func (l *SinglyLinkedList) AttachNode(node *SinglyNode) {
    if l.head == nil {
        l.head = node
    } else {
        l.last.SetNext(node)
    }
    l.last = node
    l.count++
}

func (l *SinglyLinkedList) Add(data interface{}) {
    l.AttachNode(NewSinglyNode(data))
}

func (l *SinglyLinkedList) Count() int {
    return l.count
}

func (l *SinglyLinkedList) GetNext() (*SinglyNode, error) {
    if l.head == nil {
        return nil, errors.New("list is empty")
    }
    return l.head, nil
}

func (l *SinglyLinkedList) GetByIndex(index int) (*SinglyNode, error) {
    if l.head == nil {
        return nil, errors.New("list is empty")
    }
    if index+1 > l.count {
        return nil, errors.New("index out of range")
    }
    node, _ := l.GetNext()
    for i := 0; i < index; i++ {
        node, _ = node.GetNext()
    }
    return node, nil
}

func main() {
    list := singly_linked_list.NewSinglyLinkedList()

    list.Add("One")
    list.Add("Two")
    list.Add("Three")

    firstNode, err := list.GetNext()
    if err != nil {
        panic(err)
    }

    secondNode, err := firstNode.GetNext()
    if err != nil {
        panic(err)
    }

    thirdNode, err := secondNode.GetNext()
    if err != nil {
        panic(err)
    }

    println(firstNode.ToString())  // One
    println(secondNode.ToString()) // Two
    println(thirdNode.ToString())  // Three
}

func main() {
    list := singly_linked_list.NewSinglyLinkedList()

    list.Add("One")
    list.Add("Two")
    list.Add("Three")

    node, err := list.GetByIndex(2)
    if err != nil {
        panic(err)
    }

    fmt.Println(node.ToString()) // Three
}