Go 기초 6. Linked list, Stack, Queue

JINSOO PARK·2021년 10월 14일

ADD

Remove

slice

linked list

메모리상에서 slice와 linked list

stack

컴맹을 위한 Go 언어 기초 강좌

목록 보기

9/15

Linked List

배열은 메모리상으로 한덩어리로 붙어 있지만 linked list는 메모리상에서는 떨어져 있지만 연결되어 있다.

ADD

맨끝의 노드에 다음 노드를 연결하여 이어나간다. 그러기 위해선 맨끝의 노드가 먼지 알 필요가 있다.

ex1)맨첫 노드부터 하나씩 따라가서 맨끝을 찾아서 추가하는 방식

package main

import "fmt"

type Node struct {
	next *Node // 다음 노드에 대한 포인트
	val  int
}

func main() {
	var root *Node

	root = &Node{val: 0} // root는 Node의 주소값 {val: 0}는 필드값

	for i := 1; i < 10; i++ {
		AddNode(root, i)
	}

	node := root
	for node.next != nil { // 다음 노드가 없을 때까지 반복
		fmt.Printf("%d ->", node.val)
		node = node.next
	}
	fmt.Printf("%d\n", node.val) // 현재의 노드 출력
}

func AddNode(root *Node, val int) {
	var tail *Node
	tail = root            //tail에 root를 대입
	for tail.next != nil { // 테일의 마지막이 존재하면 계속 전진
		tail = tail.next // 다음 노드를 테일에 대입
	}

	node := &Node{val: val} // 새로운 필드값 Node{val: 1} 을 주고 새로운  Node 구조체가 만들어지고 그 주소값을 초기화
	tail.next = node
}
-----------------------------
0 ->1 ->2 ->3 ->4 ->5 ->6 ->7 ->8 ->9

ex2)tail을 기억하고 있다가 추가하는 방식

package main

import "fmt"

type Node struct {
	next *Node // 다음 노드에 대한 포인트
	val  int
}

func main() {
	var root *Node
	var tail *Node // 맨끝의 노드 변수 추가

	root = &Node{val: 0}
	tail = root // 여기서 추가된 루트는 루트이자 테일

	for i := 1; i < 10; i++ {
		tail = AddNode(tail, i) // 마지막 노드를 테일로 갱신
	}

	node := root
	for node.next != nil { // 다음 노드가 없을 때까지 반복
		fmt.Printf("%d ->", node.val) // 노드 출력
		node = node.next              // 다음 노드를 대입
	}
	fmt.Printf("%d\n", node.val) // 현재의 노드 출력
}

func AddNode(tail *Node, val int) *Node { //반환값을 넣어줌
	node := &Node{val: val} // 새로운 필드값 Node{val: 1} 을 주고 새로운  Node 구조체가 만들어지고 그 주소값을 초기화
	tail.next = node        // 위의 값을 새로운 tail의 next로 들어감
	return node             // 새로 추가된 노드를 반환
}
-----------------------------
0 ->1 ->2 ->3 ->4 ->5 ->6 ->7 ->8 ->9
// 결과는 같지만 좀더 간단함

맨처음 부터 하나씩 꼬리를 찾아나갈 경우

현재있는 노드의 갯수 만큼 시간이 필요함 O(N) 즉 백만개가 있으면 백만번의 시간이 든다.

꼬리를 기억하고 있을 경우

아무리 많은 노드가 있어도 O(1) 즉 한번만 add를 하면 됨

Remove

내가 원하는 부분의 노드를 삭제한다.
링크를 끊어 reference conut를 0으로 만들어 garbage collector가 자동으로 삭제하게 많든다.

ex1) 중간 노드를 지울때

package main

import "fmt"

type Node struct {
	next *Node // 다음 노드에 대한 포인트
	val  int
}

func main() {
	var root *Node
	var tail *Node // 맨끝의 노드 변수 추가

	root = &Node{val: 0}
	tail = root // 여기서 추가된 루트는 루트이자 테일

	for i := 1; i < 10; i++ {
		tail = AddNode(tail, i) // 마지막 노드를 테일로 갱신
	}

	PrintNodes(root)

	RemoveNode(root)

	PrintNodes(root)
}

func AddNode(tail *Node, val int) *Node { //반환값을 넣어줌
	node := &Node{val: val} // 새로운 필드값 Node{val: 1} 을 주고 새로운  Node 구조체가 만들어지고 그 주소값을 초기화
	tail.next = node        // 위의 값을 새로운 tail의 next로 들어감
	return node             // 새로 추가된 노드를 반환
}

func RemoveNode(prev *Node) {
	prev.next = prev.next.next //현재 노드의 전 노드와 다음 노드
}

func PrintNodes(root *Node) {
	node := root
	for node.next != nil { // 다음 노드가 없을 때까지 반복
		fmt.Printf("%d ->", node.val) // 노드 출력
		node = node.next              // 다음 노드를 대입
	}
	fmt.Printf("%d\n", node.val) // 현재의 노드 출력
}
-------------------------------
0 ->1 ->2 ->3 ->4 ->5 ->6 ->7 ->8 ->9
0 ->2 ->3 ->4 ->5 ->6 ->7 ->8 ->9

ex2) 맨 앞의 노드를 지울때

package main

import "fmt"

type Node struct {
	next *Node // 다음 노드에 대한 포인트
	val  int
}

func main() {
	var root *Node
	var tail *Node // 맨끝의 노드 변수 추가

	root = &Node{val: 0}
	tail = root // 여기서 추가된 루트는 루트이자 테일

	for i := 1; i < 10; i++ {
		tail = AddNode(tail, i) // 마지막 노드를 테일로 갱신
	}
	PrintNodes(root)

	root, tail = RemoveNode(root, root, tail) /루트를 넣어 줌

	PrintNodes(root)

}

func AddNode(tail *Node, val int) *Node { //반환값을 넣어줌
	node := &Node{val: val} // 새로운 필드값 Node{val: 1} 을 주고 새로운  Node 구조체가 만들어지고 그 주소값을 초기화
	tail.next = node        // 위의 값을 새로운 tail의 next로 들어감
	return node             // 새로 추가된 노드를 반환
}

func RemoveNode(node *Node, root *Node, tail *Node) (*Node, *Node) {
	if node == root { // root를 없앨때
		root = root.next
		if root == nil { // 노드가 하나밖에 없을때
			tail = nil // 테일도 없어진다
		}
		return root, tail
	}
	prev := root
	for prev.next != node {
		prev = prev.next // prev의 다음 노드가 현재노드와 같아지면 포문을 빠져나옴
	}
	prev.next = prev.next.next

	if node == tail { // tail을 지우고 싶을때
		prev.next = nil // 다음 노드가 없어야됨
		tail = prev     // 한칸 건너뜀
	} else {
		prev.next = prev.next.next

	}
	return root, tail
}

func PrintNodes(root *Node) {
	node := root
	for node.next != nil { // 다음 노드가 없을 때까지 반복
		fmt.Printf("%d ->", node.val) // 노드 출력
		node = node.next              // 다음 노드를 대입
	}
	fmt.Printf("%d\n", node.val) // 현재의 노드 출력
}
------------------------------
0 ->1 ->2 ->3 ->4 ->5 ->6 ->7 ->8 ->9
1 ->2 ->3 ->4 ->5 ->6 ->7 ->8 ->9

ex3) 맨 끝 노드를 지울때

package main

import "fmt"

type Node struct {
	next *Node // 다음 노드에 대한 포인트
	val  int
}

func main() {
	var root *Node
	var tail *Node // 맨끝의 노드 변수 추가

	root = &Node{val: 0}
	tail = root // 여기서 추가된 루트는 루트이자 테일

	for i := 1; i < 10; i++ {
		tail = AddNode(tail, i) // 마지막 노드를 테일로 갱신
	}
	PrintNodes(root)

	root, tail = RemoveNode(tail, root, tail)  /테일을 넣어 줌

	PrintNodes(root)

	fmt.Println(tail.val)
}

func AddNode(tail *Node, val int) *Node { //반환값을 넣어줌
	node := &Node{val: val} // 새로운 필드값 Node{val: 1} 을 주고 새로운  Node 구조체가 만들어지고 그 주소값을 초기화
	tail.next = node        // 위의 값을 새로운 tail의 next로 들어감
	return node             // 새로 추가된 노드를 반환
}

func RemoveNode(node *Node, root *Node, tail *Node) (*Node, *Node) {
	if node == root { // root를 없앨때
		root = root.next
		if root == nil { // 노드가 하나밖에 없을때
			tail = nil // 테일도 없어진다
		}
		return root, tail
	}
	prev := root
	for prev.next != node {
		prev = prev.next // prev의 다음 노드가 현재노드와 같아지면 포문을 빠져나옴
	}
	prev.next = prev.next.next

	if node == tail { // tail을 지우고 싶을때
		prev.next = nil // 다음 노드가 없어야됨
		tail = prev     // 한칸 건너뜀
	} else {
		prev.next = prev.next.next

	}
	return root, tail
}

func PrintNodes(root *Node) {
	node := root
	for node.next != nil { // 다음 노드가 없을 때까지 반복
		fmt.Printf("%d ->", node.val) // 노드 출력
		node = node.next              // 다음 노드를 대입
	}
	fmt.Printf("%d\n", node.val) // 현재의 노드 출력
}
-----------------------------
0 ->1 ->2 ->3 ->4 ->5 ->6 ->7 ->8 ->9
0 ->1 ->2 ->3 ->4 ->5 ->6 ->7 ->8
8

Double Linked List

remove를 할때 지우고 싶은 노드의 전 노드와 그 다음 노드를 알아야 하기 때문에 이 두가지를 기록해 놓는것을 double linked list라고 한다.

ex1)

package main

import (
	"fmt"
)

type Node struct {
	next *Node // 다음 노드를 기억한다.
	prev *Node // 전의 노드를 기억한다.
	val  int
}

type LinkeList struct {
	root *Node
	tail *Node
}

func (l *LinkeList) AddNode(val int) {
	if l.root == nil { // 맨처음엔 root와 tail 둘다 nil 이기때문에
		l.root = &Node{val: val} // 새로운 노드를 만듦
		l.tail = l.root          // 하나만 있는 상태에서 root와 tail은 같음
		return
	}
	l.tail.next = &Node{val: val} // tail 의 다음 노드를 만듦
	prev := l.tail                // 이전 tail을 기억함
	l.tail = l.tail.next          // tail을 다음노드로 넣어서 제일 끝의 노드를 항상 tail로 유지
	l.tail.prev = prev            // 새로운 tail의 전노드를 prev로 기억함
}

func (l *LinkeList) RemoveNode(node *Node) {
	if node == l.root {
		l.root = l.root.next
		l.root.prev = nil
		node.next = nil
		return
	}
	prev := node.prev // 지우고자하는 로그의 이전으로

	if node == l.tail {
		prev.next = nil
		l.tail.prev = nil
		l.tail = prev
	} else {
		node.prev = nil
		prev.next = prev.next.next
		prev.next.prev = prev
	}
	node.next = nil
}

func (l *LinkeList) PrintNodes() {
	node := l.root
	for node.next != nil {
		fmt.Printf("%d ->", node.val)
		node = node.next
	}
	fmt.Printf("%d\n", node.val)
}

func main() {
	list := &LinkeList{}
	list.AddNode(0)

	for i := 1; i < 10; i++ {
		list.AddNode(i)
	}

	list.PrintNodes()

	list.RemoveNode(list.root.next)

	list.PrintNodes()

	list.RemoveNode(list.root)

	list.PrintNodes()

	list.RemoveNode(list.tail)

	list.PrintNodes()
	fmt.Printf("tail:%d\n", list.tail.val)

}
---------------------------------------
0 ->1 ->2 ->3 ->4 ->5 ->6 ->7 ->8 ->9
0 ->2 ->3 ->4 ->5 ->6 ->7 ->8 ->9
2 ->3 ->4 ->5 ->6 ->7 ->8 ->9
2 ->3 ->4 ->5 ->6 ->7 ->8
tail:8

이전 노드를 알고 있음면 역으로 출력하는것도 가능하다.

ex2) 역으로 출력

package main

import (
	"fmt"
)

type Node struct {
	next *Node // 다음 노드를 기억한다.
	prev *Node // 전의 노드를 기억한다.
	val  int
}

type LinkeList struct {
	root *Node
	tail *Node
}

<생략>

func (l *LinkeList) PrintReverse() {
	node := l.tail         // tail을 시작점으로
	for node.prev != nil { //tail의 이전이 없을때까지 진행
		fmt.Printf("%d ->", node.val) //val값 출력
		node = node.prev              //node를 이전 노드로 초기화
	}
	fmt.Printf("%d\n", node.val) // 현제 노드 출력
}

func main() {
	list := &LinkeList{}
	list.AddNode(0)

	for i := 1; i < 10; i++ {
		list.AddNode(i)
	}

	list.PrintNodes()

	list.RemoveNode(list.root.next)

	list.PrintNodes()

	list.RemoveNode(list.root)

	list.PrintNodes()

	list.RemoveNode(list.tail)

	list.PrintNodes()

	list.PrintReverse()
	fmt.Printf("tail:%d\n", list.tail.val)

}
-----------------------------------
0 ->1 ->2 ->3 ->4 ->5 ->6 ->7 ->8 ->9
0 ->2 ->3 ->4 ->5 ->6 ->7 ->8 ->9
2 ->3 ->4 ->5 ->6 ->7 ->8 ->9
2 ->3 ->4 ->5 ->6 ->7 ->8
8 ->7 ->6 ->5 ->4 ->3 ->2
tail:8

linked list와 slice의 차이점

slice

append: 기존의 데이터 하나하나 복사 하고 하나를 추가하기 때문에 O(N)이라고 할 수 있다.
remove
맨끝: 기존의 데이터(a[],6)에서 필요한 부분(a[0:5])만 가져와서 lenth의 주소만 바뀌기 때문에 O(1)이다.

맨앞: 기존의 데이터(a[],6)에서 필요한 부분(a[1:0])만 가져와서 a의 주소만 바뀌기 때문에 O(1)이다.

중간

	a := []int{1, 2, 3, 4, 5}
	a = append(a[0:2], a[3:]...)
   
	fmt.Println(a)
    ----------------------
    [1 2 4 5]

a[0]~[1]까지 끊고 a[3]부터 끝까지를 복사 해와서 붙인다. O(N)

특정 데이터를 가져올때
시작주소를 알고 있기 때문에 원하는 인덱스 x size + 시작주소 를 하면 바로 가져올 수 있어서 O(N)

linked list

add: tail을 기억하고 거기하나만 추가 하면 되기 때문에 O(1)이다.
remove: double list인 경우에 앞과 뒤를 기억하고 있기때문에 O(1)이 된다.
특정 데이터를 가져올때
특정 인덱스를 가져오고 싶을때 거기까지 전진해야된다(Randem Acess). O(N)

메모리상에서 slice와 linked list

slice: 배열로 한덩어리 이기 때문에 hdd에서 cache로 데이터를 가져올때 한번에 가져와서 작업을 처리 할 수 있다.
linked list: 각 각의 데이터가 따로 따로 떨어져 있기 때문에 cache가 주변데이터를 들고와도 주변에 필요한 데이터가 있을 확률이 적다. 그렇기 때문에 필요한 데이터가 있을때마다 hhd에서 메모리를 가져와야 되기 때문에 기존에 있던 cache가 쓸모가 없어지면서 cache miss가 나기 쉽다.

Stack,Queue

stack

FILO(first input last out)

package main

import "fmt"

func main() {
	stack := []int{}

	for i := 1; i <= 5; i++ {
		stack = append(stack, i)
	} // 1부터 순서대로 메모리에 초기화

	fmt.Println(stack) // 현재 배열에 저장된 값

	for len(stack) > 0 {
		var last int
		last, stack = stack[len(stack)-1], stack[:len(stack)-1] //last는 stack의 4번째 인덱스 값 stack은 4번째 부터 마지막 인덱스를 줄여 나간다.
		fmt.Println(last)
	}
}
-------------------------------
[1 2 3 4 5]
5
4
3
2
1

Queue
FIFO(first input first out)

package main

import "fmt"

func main() {
queue := []int{}

	for i := 1; i <= 5; i++ {
		queue = append(queue, i)
	} // 1부터 순서대로 메모리에 초기화

	fmt.Println(queue) // 현재 배열에 저장된 값

	for len(queue) > 0 {
		var front int
		front, queue = queue[0], queue[1:] //front는 queue의 0번째 인덱스 값 queue 는 1번째 인덱스로 하여 0번째 값을 없애준다.
		fmt.Println(front)
	}

}
-------------------------------

[1 2 3 4 5]
1
2
3
4
5