Integer Double Ended Queue GO

I'm currently learning Go and I have decided to implement a Circular Doubly Linked List (Deque) structure for the training. Go is not my first language. I program mainly in Python, therefore I would like to learn if code follows Go structure and idioms and if you have any advice of improving.

This is circular doubly linked list data structure, so the idea is to have O(1) add/remove/peek access to the elements at the beginning/end of the list and no access to elements between the two. I implemented methods for adding and removing elements and also to represent list as string and compare two lists. deque.test also contains test cases for each of the methods.

I use linked list here, but I acknowledge that same thing can be achieved with slices (maybe more efficiently), but my secondary goal was to get used to pointers and references - as those doesn't appear in Python.

I'm hoping for general feedback but I also have questions about specific section:

• When deque is empty and I'm trying to pop element, method would call panic to stop execution of the program, instead of returning an error. Is this a good practice in Go? Should I return value and error from pop instead (it seems a bit awkward to me to require handling possible empty list error every time an element is popped).

Project Structure

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",
},
}

$$$$
`
• Pop can return two variables an int and a bool to inform caller if queue is empty or not with bool instead of panicking or returning an error. Also you should not shadow types with variables. – Ozan Apr 26 at 21:52