В настоящее время я изучаю Go, и я решил реализовать структуру кругового двусвязного списка (Deque) для обучения. Го — не мой родной язык. Я программирую в основном на Python, поэтому я хотел бы узнать, следует ли код структуре и идиомам Go, и есть ли у вас какие-либо советы по улучшению.
О коде:
Это круговая структура данных двусвязного списка, поэтому идея состоит в том, чтобы иметь O (1) доступ для добавления / удаления / просмотра элементов в начале / конце списка и без доступа к элементам между ними. Я реализовал методы для добавления и удаления элементов, а также для представления списка в виде строки и сравнения двух списков. deque.test также содержит тестовые примеры для каждого из методов.
Здесь я использую связанный список, но я понимаю, что то же самое можно достичь с помощью срезов (возможно, более эффективно), но моей вторичной целью было привыкнуть к указателям и ссылкам — поскольку они не отображаются в Python.
Вопрос по коду:
Я надеюсь на общие отзывы, но у меня также есть вопросы по конкретному разделу:
- Когда deque пуста, и я пытаюсь извлечь элемент, метод вызовет панику, чтобы остановить выполнение программы, вместо того, чтобы возвращать ошибку. Это хорошая практика в Go? Должен ли я вместо этого возвращать значение и ошибку из pop (мне кажется немного неудобным требовать обработки возможной ошибки пустого списка каждый раз, когда элемент выталкивается).
Структура проекта
collections/
- cmd/
- - main.go
- deque/
- - deque.go
- - deque_test.go
- - node.go
- - test_cases.go
- some_other_collection/
- - ...
deque.go
// Package deque implements deque type and common methods to interact with
// deque.
package deque
import (
"strconv"
"strings"
)
// Deque is implemented as circular doubly linked list with sentinel node.
// This allows for O(1) non-amortized add/remove operations for both ends
// of the structure. This makes it a perfect implementation of queue data
// structure.
type Deque struct {
sentinel *IntNode
length int
}
// Constructor for new empty deque.
func New() Deque {
sentinel := &IntNode{0, nil, nil}
sentinel.prev = sentinel
sentinel.next = sentinel
return Deque{sentinel, 0}
}
// Constructor for new empty deque populated with elements from slice.
func FromSlice(slice []int) Deque {
deq := New()
for _, val := range slice {
deq.Append(val)
}
return deq
}
// Append adds element to the end of the deque.
func (d *Deque) Append(elem int) {
newNode := IntNode{value: elem, next: d.sentinel, prev: d.sentinel.prev}
d.sentinel.prev.next = &newNode
d.sentinel.prev = &newNode
d.length += 1
}
// AppendLeft adds element to the front of the deque.
func (d *Deque) AppendLeft(elem int) {
newNode := IntNode{value: elem, next: d.sentinel.next, prev: d.sentinel}
d.sentinel.next.prev = &newNode
d.sentinel.next = &newNode
d.length += 1
}
// Pop removes and returns last element in deque.
func (d *Deque) Pop() int {
if d.Empty() {
panic("popping from empty list")
}
value := d.sentinel.prev.value
d.sentinel.prev.prev.next = d.sentinel
d.sentinel.prev = d.sentinel.prev.prev
d.length -= 1
return value
}
// Pop removes and returns first element in deque.
func (d *Deque) PopLeft() int {
if d.Empty() {
panic("popping from empty list")
}
value := d.sentinel.next.value
d.sentinel.next.next.prev = d.sentinel
d.sentinel.next = d.sentinel.next.next
d.length -= 1
return value
}
// Last return value of the first element in deque.
func (d *Deque) First() int {
return d.sentinel.next.value
}
// Last return value of the last element in deque.
func (d *Deque) Last() int {
return d.sentinel.prev.value
}
// Length returns number of elements in deque.
func (d *Deque) Length() int {
return d.length
}
// Empty checks if there are any elements in deque.
func (d *Deque) Empty() bool {
return d.length == 0
}
// String outputs string representation of deque.
func (d *Deque) String() string {
var b strings.Builder
curr := d.sentinel.next
b.WriteString("Deque{")
for i := 0; i < d.Length(); i++ {
b.WriteString(strconv.Itoa(curr.value))
b.WriteString(",")
curr = curr.next
}
b.WriteString("}")
return b.String()
}
// Equals checks if both deques contain same elements in the same order.
func (d *Deque) Equals(other *Deque) bool {
if d.Length() != other.Length() {
return false
}
curr := d.sentinel.next
otherCurr := other.sentinel.next
for i := 0; i < d.Length(); i++ {
if curr.value != otherCurr.value {
return false
}
curr = curr.next
otherCurr = otherCurr.next
}
return true
}
node.go
package deque
type IntNode struct {
value int
next *IntNode
prev *IntNode
}
deque_test.go
package deque
import (
"testing"
"github.com/stretchr/testify/assert"
)
func TestEquals(t *testing.T) {
for _, tc := range TestCasesEquals {
if tc.this.Equals(&tc.other) != tc.expected {
t.Errorf(tc.msg)
}
}
}
func TestAppend(t *testing.T) {
for _, tc := range TestCasesAppend {
actual := tc.actual()
if !actual.Equals(&tc.expected) {
t.Errorf(tc.msg)
}
}
}
func TestAppendLeft(t *testing.T) {
for _, tc := range TestCasesAppendLeft {
actual := tc.actual()
if !actual.Equals(&tc.expected) {
t.Errorf(tc.msg, actual, tc.expected)
}
}
}
func TestPop(t *testing.T) {
// Main test cases
for _, tc := range TestCasesPop {
deque, popped := tc.actual()
if !deque.Equals(&tc.expectedDeque) || popped != tc.expectedPopped {
t.Errorf(tc.msg)
}
}
// Popping from empty list
poppingEmpty := func() {
d := FromSlice([]int{})
d.Pop()
}
assert.Panics(t, poppingEmpty, "popping from empty deque")
}
func TestPopLeft(t *testing.T) {
// Main test cases
for _, tc := range TestCasesPopLeft {
deque, popped := tc.actual()
if !deque.Equals(&tc.expectedDeque) || popped != tc.expectedPopped {
t.Errorf(tc.msg)
}
}
// Popping from empty list
poppingEmpty := func() {
d := FromSlice([]int{})
d.Pop()
}
assert.Panics(t, poppingEmpty, "popping from empty deque")
}
func TestString(t *testing.T) {
d := New()
if d.String() != "Deque{}" {
t.Errorf("empty deque; got: %v", d.String())
}
d = FromSlice([]int{1, 2, 7, 4})
if d.String() != "Deque{1,2,7,4,}" {
t.Errorf("4 element deque; got: %v", d.String())
}
}
test_cases.go
package deque
type TestCaseEquals struct {
this Deque
other Deque
expected bool
msg string
}
var TestCasesEquals = []TestCaseEquals{
{
this: New(),
other: New(),
expected: true,
msg: "two empty deques",
},
{
this: FromSlice([]int{1, 2, 3}),
other: FromSlice([]int{1, 2, 3}),
expected: true,
msg: "two identical, 3-element deques",
},
{
this: FromSlice([]int{1, 2, 3}),
other: FromSlice([]int{1, 2, 4}),
expected: false,
msg: "same length, last element mismatching",
},
{
this: FromSlice([]int{1, 2, 3}),
other: FromSlice([]int{1, 2}),
expected: false,
msg: "different length, elements matching",
},
}
type TestCaseAppend struct {
actual func() Deque
expected Deque
msg string
}
var TestCasesAppend = []TestCaseAppend{
{
actual: func() Deque {
return New()
},
expected: New(),
msg: "2 empty deques",
},
{
actual: func() Deque {
d := New()
d.Append(1)
return d
},
expected: FromSlice([]int{1}),
msg: "adding one element to deque",
},
{
actual: func() Deque {
d := New()
d.Append(1)
d.Append(3)
d.Append(5)
d.Append(19)
return d
},
expected: FromSlice([]int{1, 3, 5, 19}),
msg: "adding multiple elements to deque",
},
}
var TestCasesAppendLeft = []TestCaseAppend{
{
actual: func() Deque {
d := New()
d.AppendLeft(1)
return d
},
expected: FromSlice([]int{1}),
msg: "adding one element to deque. Got: %v, Expected: %v",
},
{
actual: func() Deque {
d := New()
d.AppendLeft(1)
d.AppendLeft(3)
d.AppendLeft(5)
d.AppendLeft(19)
return d
},
expected: FromSlice([]int{19, 5, 3, 1}),
msg: "adding multiple elements to deque. Got: %v, Expected: %v",
},
}
type TestCasePop struct {
actual func() (Deque, int)
expectedDeque Deque
expectedPopped int
msg string
}
var TestCasesPop = []TestCasePop{
{
actual: func() (Deque, int) {
d := FromSlice([]int{1})
val := d.Pop()
return d, val
},
expectedDeque: New(),
expectedPopped: 1,
msg: "popping from deque with 1 element",
},
{
actual: func() (Deque, int) {
d := FromSlice([]int{1, 2, 3})
val := d.Pop()
return d, val
},
expectedDeque: FromSlice([]int{1, 2}),
expectedPopped: 3,
msg: "popping from deque with 3 elements",
},
{
actual: func() (Deque, int) {
d := FromSlice([]int{1, 2, 3})
d.Pop()
val := d.Pop()
return d, val
},
expectedDeque: FromSlice([]int{1}),
expectedPopped: 2,
msg: "popping twice from deque with 3 elements",
},
}
var TestCasesPopLeft = []TestCasePop{
{
actual: func() (Deque, int) {
d := FromSlice([]int{1})
val := d.PopLeft()
return d, val
},
expectedDeque: New(),
expectedPopped: 1,
msg: "popping from deque with 1 element",
},
{
actual: func() (Deque, int) {
d := FromSlice([]int{1, 2, 3})
val := d.PopLeft()
return d, val
},
expectedDeque: FromSlice([]int{2, 3}),
expectedPopped: 1,
msg: "popping from deque with 3 elements",
},
{
actual: func() (Deque, int) {
d := FromSlice([]int{1, 2, 3})
d.PopLeft()
val := d.PopLeft()
return d, val
},
expectedDeque: FromSlice([]int{3}),
expectedPopped: 2,
msg: "popping twice from deque with 3 elements",
},
}
```