Hello World! Here is Switch. Having introduce the bases of programming, it is time to go a bit deeper. This post will start a serie about data structure. Data structure defines solution to manage data set in a program and using the correct structure will greatly improve code performance. Also, a good structure will simplify the implementation of problem resolution.
As a first post around data structure, I will introduce the basic Chained List structure.
Structure description
A chain list build upon a single entry point witch represent the Head of the list. The head stores a value and a reference (pointer) to the next listed elements. It has no index notion and is a first in, last out structure. It means that you will neither have a direct access to a known element of the list without depilating all heads before the elements and the first element to be added will be retrieved last.
When defining a list, we have to provide user with basic function to manipulate it. We also like to define more advanced powerful tools.
Essentials feature to provide is a Prepend method to add element to a list. You also have to provide a Head et un Tail function to retrieve the first element and queue of current list head.
For advanced tools, I like to provide a Sort method witch will allow you to reorder list elements and a Map function. The Map function allows you to apply a method to each element composing the list. If I call Map with a times two function on the [9,1,12] list, it should return me the [18,2,24] list.
Pseudo code defintion
Now, let’s propose a pseudo code definition of the list structure. I will introduce a new keywords to our pseudo code: define NAME { Properties list }. It will create a structure named NAME containing specific values. I can associate methods to this structure using func NAME(Variable).Method notation and properties listed in the structure can be accessed through NAME.Property.
Let’s define the basic structure and methods.
define List {
Head any
Tail List
}
emptyList = List{} // I expect emptyList to be a global constant.
func NewList() List {
return emptyList
}
func List(l).Prepend(element any) List {
return List{
Head<-element
Tail<-l
}
}
func List(l).Pop() any, List {
return l.Head, l.Tail
}Our list structure keeps track of its head and tail by relying on an internal propertie Head and Tail. Head is any value you wish to add to the list and Tail the reference to next part. I define an emptyList constant so we can easily identify it. NewList create an empty list where you will be able to add elements. Prepend method takes the value you provide to it and build a new List structure using current List element as Tail. Finally, the Pop method will return you a couple containing the Head value of the list and the full Tail list.
Then let’s simply sort the list. I will propose the basic bubble sort implementation. To bubble sort a list, you need to sort its tail then add the head at the current place in the sorted list. Witch will give something like:
func List(l).SortedAdd(element any, comp function) List {
if l == emptyList {
return emptyList
}
if comp(element, l.Head) is True {
return List{Head<-element, Tail<-l}
}
return List{Head<-l.Head,Tail<-l.Tail.SortedAdd(element, comp)}
}
func List(l).Sort(comp function) List {
if l == emptyList {
return l
}
sorted = l.Tail.Sort()
return sorted.Add()
}Finally, let’s define the Map method. Map will go through each Head element in List, apply provided method and build a new list element using this newly computed value and the application of Map to its Tail.
func List(l).Map(fn function) List {
if l == emptyList {
return emptyList
}
return List{Head<-fn(l.Head),Tail<-l.Tail.Map(fn)}
}Now let’s code it in Go.
Test definition
We will start by defining a code process for our list. We know that we will create a List structure witch will contained a Head of type interface{} (interface is a neutral type in Go) and the Tail will contained a recursive call to List type. For this structure, we wish to define an Empty value and an asserter for emptiness. We also wish the constructor of list type to provide an Empty list. A first test would then be:
– When I create a new list
– I expect it to be an Empty list
func TestNewList(t *testing.T) {
Convey("When I create a list", t, func() {
newList := list.New()
Convey("I expect it to be empty", func() {
So(newList.Empty(), ShouldBeTrue)
})
})
}Then we would like to add element to a list. After adding an element, I should ensure the updated list is not empty, as a Head value equal to provided data, and has a tail equals to initial list. The test protocol would be:
– Given I have an empty list
– When I add an element X
– List should not be Empty
– Head should equal X
– Tail should be empty
– Given I have a list L
– When I add an element X stored as newL
– newL should not be Empty
– newL Head should equal X
– newL Tail should equal L
Convey("Given I have ", t, func() {
Convey("an Empty list", func() {
l := list.New()
Convey("When I add an element X", func() {
newL := l.Prepend("X")
So(newL.Empty(), ShouldBeFalse)
So(newL.Head, ShouldEqual, "X")
So(newL.Queue.Empty(), ShouldBeTrue)
})
})
Convey("a list", func() {
l := list.New().Prepend("X").Prepend("Y").Prepend("Z")
Convey("When I add an element X", func() {
newL := l.Prepend("A")
So(newL.Empty(), ShouldBeFalse)
So(newL.Head, ShouldEqual, "A")
So(*newL.Queue, ShouldResemble, l)
})
})
})Then we can define test protocol for Pop:
– Given an Empty list L
– L.Pop() should return nil, EmptyList
– Given a [3,4,5] list L
– L.Pop() should return 3, [4,5] as H, L2
– L2.Pop() should return 4, [5]
Convey("Given", t, func() {
Convey("an Empty list", func() {
l := list.New()
h, q := l.Pop()
So(h, ShouldBeNil)
So(q.Empty(), ShouldBeTrue)
})
Convey("a known list", func() {
l := list.New().Prepend(5).Prepend(4)
l2 := l.Prepend(3)
h, q := l2.Pop()
So(h, ShouldEqual, 3)
So(q, ShouldResemble, l)
h2, _ := q.Pop()
So(h2, ShouldEqual, 4)
})
})Now, we should ensure Map function will behave.
– Given an Empty List L
– L.Map(func(e interface{}) {return e}) should return Empty List
– Given a single element list L = [“hello”]
– And a function addWorld witch add ” world!” to string interface
– When I call L.Map(addWorld)
– Then I should have [“hello world!”] list
– Given a list L = [“hello”, “my”, “new”]
– And a function addWorld witch add ” world!” to string interface
– When I call L.Map(addWorld)
– Then I should have [“hello world!”, “my world!”, “new world!”] list
func TestList_Map(t *testing.T) {
Convey("Given ", t, func() {
Convey("an Empty list", func() {
l := list.New()
Convey("when I apply Map function", func() {
newL := l.Map(func(e interface{}) interface{} { return e })
So(newL.Empty(), ShouldBeTrue)
})
})
l := list.New()
addWorld := func(e interface{}) interface{} { return e.(string) + " world!" }
Convey("a single element list", func() {
l = l.Prepend("hello")
expectedL := list.New().Prepend("hello world!")
Convey("when I apply Map function", func() {
newL := l.Map(addWorld)
So(*newL, ShouldResemble, expectedL)
})
})
Convey("a list", func() {
l = l.Prepend("new").Prepend("my").Prepend("hello")
expectedL := list.New().Prepend("new world!").Prepend("my world!").Prepend("hello world!")
Convey("when I apply Map function", func() {
newL := l.Map(addWorld)
So(*newL, ShouldResemble, expectedL)
})
})
})
}Finally, we should safe the sort function. Again, sort function should not alter empty or single element list. Also, given a sorted list, the list should stay sorted and given a randomly ordered list.
func TestList_BullSort(t *testing.T) {
Convey("Given a list", t, func() {
tmpList := list.New().Prepend(1).Prepend(4).Prepend(6).Prepend(9).Prepend(3).Prepend(5).Prepend(2).Prepend(10)
expectedSorted := list.New().
Prepend(1).Prepend(2).Prepend(3).Prepend(4).Prepend(5).
Prepend(6).Prepend(9).Prepend(10)
l := &tmpList
comp := func(a, b interface{}) bool {
return a.(int) > b.(int)
}
Convey("empty or single element, should stay as his", func() {
})
Convey("not sorted, I should be able to sort it", func() {
func TestList_BullSort(t *testing.T) {
Convey("Given a list", t, func() {
tmpList := list.New().Prepend(1).Prepend(4).Prepend(6).Prepend(9).Prepend(3).Prepend(5).Prepend(2).Prepend(10)
expectedSorted := list.New().
Prepend(1).Prepend(2).Prepend(3).Prepend(4).Prepend(5).
Prepend(6).Prepend(9).Prepend(10)
l := &tmpList
comp := func(a, b interface{}) bool {
return a.(int) > b.(int)
}
Convey("empty or single element, should stay as his", func() {
l := list.New()
So(l.BullSort(comp), ShouldResemble, &l)
l = list.New().Prepend(1)
So(l.BullSort(comp), ShouldResemble, &l)
})
Convey("not sorted, I should be able to sort it", func() {
l = l.BullSort(comp)
So(*l, ShouldResemble, expectedSorted)
})
Convey("sorted, I should be able to sort it", func() {
l = l.BullSort(comp)
l = l.BullSort(comp)
So(*l, ShouldResemble, expectedSorted)
})
})
}Then, we just have to complete our code until test pass.
Implementation
package list
// List represents a simple chained list.
// Head provides the element
type List struct {
Head interface{}
Tail *List
}
// MapFunc abstracts Map method arguments type
type MapFunc func(element interface{}) interface{}
// New initialize an empty list
func New() List {
return List{Tail: nil, Head: nil}
}
// Empty asserts list is an empty list.
func (l List) Empty() bool {
return l.Head == nil && l.Tail == nil
}
// Prepend adds elements to list head.
func (l List) Prepend(elem interface{}) List {
return List{
Head: elem,
Tail: &l,
}
}
// Pop recovers head and queue
func (l List) Pop() (head interface{}, queue List) {
if l.Empty() {
return nil, l
}
return l.Head, *l.Tail
}
// Map applies a function to each element of a list
func (l *List) Map(fn MapFunc) *List {
if l.Empty() {
return l
}
return &List{
Head: fn(l.Head),
Tail: l.Tail.Map(fn),
}
}
// AddSorted adds an element to sorted list at the right place.
// /!\ function will not work correctly on non sorted list.
func (l *List) AddSorted(e interface{}, comp func(interface{}, interface{}) bool) *List {
if l.Empty() {
return &List{Head: e, Tail: l}
}
if comp(e, l.Head) {
return &List{Head: e, Tail: l}
}
return &List{Head: l.Head, Tail: l.Tail.AddSorted(e, comp)}
}
// BullSort sorts a list
func (l *List) BullSort(comp func(interface{}, interface{}) bool) *List {
if l.Empty() {
return l
}
sorted := l.Tail.BullSort(comp)
return sorted.AddSorted(l.Head, comp)
}You will find all code written in this article on github: https://github.com/switchelven/data-structure
That’s all folks. See you later.
