1
\$\begingroup\$

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

```
\$\endgroup\$
1
  • \$\begingroup\$ 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. \$\endgroup\$ – Ozan Apr 26 at 21:52

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.