**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()
}
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()
}
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)
}
Top comments (0)