# 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.

About the code:

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.

Question about the code:

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