1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
package main
 
import (
        "fmt"
        "log"
)
 
type Node struct {
        Data int
        Next *Node
        Prev *Node
}
 
type CDLList struct {
        Count int
        Head *Node // 가변 헤드
}
 
func IllegalBounds() {
        log.Fatal("Out of bounds!")
}
 
func NewCDLList() *CDLList {
        return &CDLList{0, nil}
}
 
func (l *CDLList) AddFirst(data int) {
        l.Head = &Node{data, nil, nil}
        l.Head.Next = l.Head
        l.Head.Prev = l.Head
        l.Count++
}
 
// 기존 Head를 Next 방향으로 밀어내고 새 Head로써 삽입
// 첫 노드는 AddFirst로 넘김
func (l *CDLList) Prepend(data int) {
        if l.Count > 0 {
                l.Head = &Node{data, l.Head, l.Head.Prev}
                l.Head.Next.Prev = l.Head
                l.Head.Prev.Next = l.Head
        } else if l.Count == 0 {
                l.AddFirst(data)
        } else {
                IllegalBounds()
        }
        l.Count++
}
 
// Head의 Prev를 Prev 방향으로 밀어내고 삽입
// 첫 노드는 AddFirst로 넘김
func (l *CDLList) Append(data int) {
        if l.Count > 0 {
                l.Head.Prev = &Node{data, l.Head, l.Head.Prev}
                l.Head.Prev.Prev.Next = l.Head.Prev
        } else if l.Count == 0 {
                l.AddFirst(data)
        } else {
                IllegalBounds()
        }
        l.Count++
}
 
// 0/양수면 Next 방향, 음수면 Prev 방향으로 인덱싱
// 추가가 아닌 삽입이므로 기존에 노드가 0개면 에러
func (l *CDLList) Insert(index int, data int) {
        if index >= 0 {
                if index > l.Count - 1 {
                        IllegalBounds()
                }
                node := l.Head
                for i := 0; i < index; i++ {
                        node = node.Next
                }
                node.Prev = &Node{data, node, node.Prev}
                node.Prev.Prev.Next = node.Prev
        } else {
                if index < -l.Count {
                        IllegalBounds()
                }
                node := l.Head.Prev
                for i := -1; i > index; i-- {
                        node = node.Prev
                }
                node.Prev = &Node{data, node, node.Prev}
                node.Prev.Prev.Next = node.Prev
        }
        l.Count++
}
 
// 0/양수면 Next 방향, 음수면 Prev 방향으로 인덱싱
func (l *CDLList) Delete(index int) {
        if index >= 0 {
                if index > l.Count - 1 {
                        IllegalBounds()
                }
                node := l.Head
                for i := 0; i < index; i++ {
                        node = node.Next
                }
                node.Prev.Next, node.Next.Prev = node.Next, node.Prev
        } else {
                if index < -l.Count {
                        IllegalBounds()
                }
                node := l.Head.Prev
                for i := -1; i > index; i-- {
                        node = node.Prev
                }
                node.Prev.Next, node.Next.Prev = node.Next, node.Prev
        }
        l.Count--
}
 
// 0/양수면 Next 방향, 음수면 Prev 방향으로 인덱싱
func (l *CDLList) Value(index int) int {
        if index >= 0 {
                if index > l.Count - 1 {
                        IllegalBounds()
                }
                node := l.Head
                for i := 0; i < index; i++ {
                        node = node.Next
                }
                return node.Data
        } else {
                if index < -l.Count {
                        IllegalBounds()
                }
                node := l.Head.Prev
                for i := -1; i > index; i-- {
                        node = node.Prev
                }
                return node.Data
        }
}
 
func (l *CDLList) Size() int {
        return l.Count
}
 
func (l *CDLList) PrintForward() {
        if l.Count > 0 {
                node := l.Head
                fmt.Println(node.Data)
                for node != l.Head.Prev {
                        node = node.Next
                        fmt.Println(node.Data)
                }
        } else {
                IllegalBounds()
        }
}
 
func (l *CDLList) PrintBackward() {
        if l.Count > 0 {
                node := l.Head.Prev
                fmt.Println(node.Data)
                for node != l.Head {
                        node = node.Prev
                        fmt.Println(node.Data)
                }
        } else {
                IllegalBounds()
        }
}
 
func main() {
        l := NewCDLList()
 
        l.AddFirst(3) // Prepend나 Append도 이용 가능
 
        l.Prepend(2)
        l.Prepend(1)
        l.Prepend(1)
        l.Prepend(0)
 
        l.Delete(2)
 
        l.Append(4)
        l.Append(6)
 
        l.Insert(5, 5)
 
 
        // 0, 1, 2, 3, 4, 5, 6
 
        l.PrintForward()
        l.PrintBackward()
 
        fmt.Println(l.Size())
        fmt.Println(l.Value(3))
        fmt.Println(l.Value(-2))
}
cs

 

수년 전에 C로 만들어보고 한번도 안 만들어보다가 갑자기 생각나서 Go로 만들어봄. Head를 원래 이렇게 처리했었나 생각이 안나는데, 그렇다고 인터넷에서 소스를 보면 재미없으니 그냥 막 만들어봤다. 그래서 효율성은 떨어질지도 모름 ㅋㅋ

C 대비 다른 점은 GC의 존재 및 . 연산자의 기능 확장. 비슷한 점은 구조체와 포인터.