DEV Community

vinay
vinay

Posted on

Singly ,Doubly ,Circular Linked List in golang....

**Types of Linked List - Singly linked, doubly linked and circular
In this tutorial, you will learn different types of linked list. Also, you will find implementation of linked list in golang.

Before you learn about the type of the linked list, make sure you know about the LinkedList Data Structure.

There are three common types of Linked List.

Singly Linked List
Doubly Linked List
Circular Linked List
**_

**Singly Linked List in golang**
package main

import (
    "fmt"
    "sort"
)

type Node struct {
    data int
    next *Node
}

type Slink struct {
    head *Node
    tail *Node
}

func (l *Slink) append(n int) {
    newNode := &Node{data: n}
    if l.head == nil {
        l.head = newNode
    } else {
        l.tail.next = newNode
    }
    l.tail = newNode
}

func (l *Slink) push(n int, pos int) {
    if pos == 0 {
        newNode := &Node{data: n}
        newNode.next = l.head
        l.head = newNode
    } else if pos > 0 && pos < l.len() {
        newNode := &Node{data: n}
        p := l.head
        i := 0
        for i < pos-1 {
            p = p.next
            i += 1
        }
        newNode.next = p.next
        p.next = newNode
    } else {
        newNode := &Node{data: n}
        l.tail.next = newNode
        l.tail = newNode
    }

}
func (l *Slink) len() int {
    p := l.head
    count := 0
    for p != nil {
        p = p.next
        count++
    }
    return count

}

func (l *Slink) pop(pos int) int {
    b := 0
    if pos == 0 {
        temp := l.head
        l.head = l.head.next
        b = temp.data
        temp.next = nil
    } else if pos > 0 && pos < l.len()-1 {
        p := l.head
        i := 0
        for i < pos-1 {
            p = p.next
            i += 1
        }
        temp := p.next
        p.next = p.next.next
        b = temp.data
        temp.next = nil
    } else {
        p := l.head
        for p.next != l.tail {
            p = p.next
        }
        b = p.next.data
        l.tail = p
        p.next = nil
    }
    return b
}

func (l *Slink) Reverse() *Node {
    var prev *Node
    currNode := l.head
    nextNode := l.head
    for nextNode != l.tail {
        prev = currNode
        nextNode = nextNode.next
        currNode.next = prev
        //prev = currNode
        currNode = nextNode
    }

    p := prev
    for p != nil {
        fmt.Print(p.data, " ")
        p = p.next
    }

    return prev

}
func (l *Slink) sort() {
    var a []int
    p := l.tail
    for p != nil {
        a = append(a, p.data)
        p = p.next
    }
    sort.Ints(a)
    newNode := &Node{}
    s := newNode
    for _, v := range a {
        s.next = &Node{data: v}
        s = s.next
    }
    q := newNode.next
    for q != nil {
        fmt.Print(q.data, " ")
        q = q.next
    }

}
func (l *Slink) display() {
    p := l.head
    for p != nil {
        fmt.Print(p.data, " ")
        p = p.next
    }

}
func disp(n *Node) {
    for n != nil {
        fmt.Print(n.data, " ")
        n = n.next
    }

}

func main() {
    l := Slink{}
    l.append(20)
    l.append(10)
    l.append(2)
    l.append(3)
    l.append(4)
    l.append(60)
    l.push(70, 5)
    l.pop(7)
    l.display()
    fmt.Println()
    fmt.Println()
    // b := l.Reverse()
    // disp(b)
    // fmt.Println("")
    // l.sort()
    l.Reverse()

}
Enter fullscreen mode Exit fullscreen mode

Doubly Linked List in golang

package main

import "fmt"

type Node struct {
    data int
    next *Node
    prev *Node
}
type Dlink struct {
    head *Node
    tail *Node
}

func (l *Dlink) append(n int) {
    newNode := &Node{data: n}
    if l.head == nil {
        l.head = newNode
    } else {
        l.tail.next = newNode
        newNode.prev = l.tail
    }
    l.tail = newNode
}

func (l *Dlink) push(n int, pos int) {
    if pos == 0 {
        newNode := &Node{data: n}
        temp := l.head
        l.head.prev = newNode
        newNode.next = temp
        l.head = newNode
    } else if pos > 0 && pos < l.len()-1 {
        newNode := &Node{data: n}
        temp := l.head
        i := 0
        for i < pos-1 {
            temp = temp.next
            i += 1
        }
        newNode.prev = temp
        newNode.next = temp.next
        temp.next.prev = newNode
        temp.next = newNode
    } else {
        newNode := &Node{data: n}
        temp := l.tail
        newNode.prev = temp
        temp.next = newNode
        l.tail = newNode

    }
}

func (l *Dlink) pop(pos int) {
    if pos == 0 {
        temp := l.head
        l.head = temp.next
        l.head.prev = nil
        temp.next = nil
    } else if pos > 0 && pos < l.len()-1 {
        p := l.head
        i := 0
        for i < pos-1 {
            p = p.next
            i += 1
        }
        temp := p.next
        p.next = temp.next
        temp.next.prev = temp
        temp.next = nil
        temp.prev = nil
    } else {
        temp := l.tail
        l.tail = l.tail.prev
        l.tail.next = nil
        temp.prev = nil
        temp.next = nil
    }
}
func (l *Dlink) len() int {
    p := l.head
    count := 0
    for p != nil {
        count++
        p = p.next
    }
    return count

}

func (l *Dlink) reverce() {
    var prev *Node
    cuurentNode := l.head
    nextNode := l.head
    for nextNode != nil {
        nextNode = nextNode.next
        cuurentNode.next = prev
        prev = cuurentNode
        cuurentNode = nextNode
    }
    // temp := l.head
    l.head, l.tail = l.tail, l.head
    // l.tail = temp
    p := prev
    fmt.Println(l.head.data)
    for p != nil {
        fmt.Print(p.data, " ")
        p = p.next
    }
    fmt.Println("")
    fmt.Println(l.tail.data)

}
func (l *Dlink) display() {
    p := l.head
    fmt.Println(l.head.data)
    for p != nil {
        fmt.Print(p.data, " ")
        p = p.next
    }
    fmt.Println("")
    fmt.Println(l.tail.data)
}
func main() {
    l := Dlink{}
    l.append(10)
    l.append(20)
    l.append(30)
    l.append(40)
    l.append(50)
    l.append(60)
    l.push(200, 6)
    l.reverce()

}
Enter fullscreen mode Exit fullscreen mode

Circular Linked List in golang

package main

import (
    "fmt"
)

type Node struct {
    data int
    next *Node
}

type slinkh struct {
    tail *Node
}

func (l *slinkh) creat(n int) {
    newNode := &Node{data: n}
    if l.tail == nil {
        l.tail = newNode
        l.tail.next = newNode
    } else {
        newNode.next = l.tail.next
        l.tail.next = newNode
        l.tail = newNode
    }

}

func (l *slinkh) push(n int, pos int) {
    if pos == 0 {
        newNode := &Node{data: n}
        newNode.next = l.tail.next
        l.tail.next = newNode
    } else if pos >= l.len() {
        newNode := &Node{data: n}
        newNode.next = l.tail.next
        l.tail.next = newNode
        l.tail = newNode
    } else if pos > 0 && pos < l.len() {
        newNode := &Node{data: n}
        i := 1
        p := l.tail
        for i < pos {
            p = p.next
            i += 1
        }
        newNode.next = p.next
        p.next = newNode
    }
}

func (l *slinkh) pop(pos int) {
    if pos == 0 {
        temp := l.tail.next.next
        l.tail.next = temp
        temp = nil
        // fmt.Println("")
        // fmt.Println(l.tail.next.next.data)
    } else if pos >= l.len()-1 {
        p := l.tail
        for p.next.next != l.tail {
            p = p.next
        }
        temp := l.tail.next
        p.next.next = temp
        l.tail = p.next
        temp = nil
    } else if pos > 0 && pos < l.len() {
        p := l.tail
        i := 1
        for i < pos {
            p = p.next
            i += 1
        }
        temp := p.next.next
        p.next.next = temp.next
        temp.next = nil
    }
}

func (l *slinkh) len() int {
    temp := l.tail
    count := 1
    for l.tail != temp.next {
        count += 1
        temp = temp.next
    }
    return count
}

func (l *slinkh) reverse() {
    var prev, currNode, nextNode *Node
    currNode = l.tail.next
    nextNode = currNode.next
    for currNode != l.tail {
        prev = currNode
        currNode = nextNode
        nextNode = currNode.next
        currNode.next = prev
    }
    nextNode.next = l.tail
    l.tail = nextNode
    p := l.tail
    temp := l.tail
    for l.tail != temp.next {
        temp = temp.next
        fmt.Print(temp.data, " ")
    }
    fmt.Print(p.data)
}

func (l *slinkh) disp() {
    p := l.tail
    temp := l.tail
    for l.tail != temp.next {
        temp = temp.next
        fmt.Print(temp.data, " ")
    }
    fmt.Print(p.data)

}

func main() {
    l := slinkh{}
    l.creat(10)
    l.creat(20)
    l.creat(30)
    l.creat(40)
    l.creat(50)
    // l.push(100, 1)
    // l.push(300, 6)
    // l.pop(4)
    l.reverse()
    // l.disp()
    // b := l.len()
    // fmt.Println("")
    // fmt.Println(b)

}

Enter fullscreen mode Exit fullscreen mode

Top comments (0)