{"id":136,"date":"2021-02-04T23:05:40","date_gmt":"2021-02-04T22:05:40","guid":{"rendered":"https:\/\/tutos.switchelven.fr\/?p=136"},"modified":"2021-02-04T23:05:40","modified_gmt":"2021-02-04T22:05:40","slug":"data-structure-chained-list","status":"publish","type":"post","link":"https:\/\/tutos.switchelven.fr\/fr\/data-structure-chained-list\/","title":{"rendered":"Data structure: Chained List"},"content":{"rendered":"\n

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<\/strong>. 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. <\/p>\n\n\n\n

As a first post around data structure, I will introduce the basic Chained List<\/strong> structure. <\/p>\n\n\n\n

Structure description<\/p>\n\n\n\n

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.<\/p>\n\n\n\n

\"\"
Graphical representation of list: [9,1,12]<\/figcaption><\/figure>\n\n\n\n

When defining a list, we have to provide user with basic function to manipulate it. We also like to define more advanced powerful tools.<\/p>\n\n\n\n

Essentials feature to provide is a Prepend<\/em> method to add element to a list. You also have to provide a Head<\/em> and a Tail<\/em> function to retrieve the first element and queue of current list head.<\/p>\n\n\n\n

For advanced tools, I like to provide a Sort<\/em> method witch will allow you to reorder list elements and a Map<\/em> function. The Map<\/em> function allows you to apply a method to each element composing the list. If I call Map<\/em> with a times two <\/em>function on the [9,1,12]<\/em> list, it should return me the [18,2,24]<\/em> list.<\/p>\n\n\n\n

Pseudo code defintion<\/p>\n\n\n\n

Now, let’s propose a pseudo code definition of the list structure. I will introduce a new keywords to our pseudo code: define<\/em> NAME { Properties list <\/em>}. It will create a structure named NAME containing specific values. I can associate methods to this structure using func NAME(Variable).Method<\/em> notation and properties listed in the structure can be accessed through NAME.Property<\/em>. <\/p>\n\n\n\n

Let’s define the basic structure and methods.<\/p>\n\n\n\n

define List {\n  Head any\n  Tail List\n}\n\nemptyList = List{} \/\/ I expect emptyList to be a global constant.\n\nfunc NewList() List {\n   return emptyList\n}\n\nfunc List(l).Prepend(element any) List {\n   return List{\n        Head<-element\n        Tail<-l\n   }\n}\n\nfunc List(l).Pop() any, List {\n    return l.Head, l.Tail\n}<\/code><\/pre>\n\n\n\n
Our list structure keeps track of its head and tail by relying on an internal propertie Head and Tail. Head<\/em> is any value you wish to add to the list and Tail<\/em> the reference to next part. I define an emptyList<\/em> constant so we can easily identify it. NewList<\/em> create an empty list where you will be able to add elements. Prepend<\/em> method takes the value you provide to it and build a new List<\/em> structure using current List<\/em> element as Tail<\/em>. Finally, the Pop<\/em> method will return you a couple containing the Head<\/em> value of the list and the full Tail<\/em> list.<\/p>\n\n\n\n
Then let’s simply sort the list. I will propose the basic bubble sort<\/em> implementation. To bubble sort<\/em> 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:<\/p>\n\n\n\n
func List(l).SortedAdd(element any, comp function) List {\n     if l == emptyList {\n         return emptyList\n     }\n\n     if comp(element, l.Head) is True {\n          return List{Head<-element, Tail<-l}\n     }\n\n     return List{Head<-l.Head,Tail<-l.Tail.SortedAdd(element, comp)}\n}\n\nfunc List(l).Sort(comp function) List {\n     if l == emptyList {\n          return l\n     }\n     \n     sorted = l.Tail.Sort()\n     return sorted.Add()\n}<\/code><\/pre>\n\n\n\n
Finally, let’s define the Map<\/em> method. Map<\/em> will go through each Head<\/em> element in List<\/em>, apply provided method and build a new list element using this newly computed value and the application of Map<\/em> to its Tail<\/em>.<\/p>\n\n\n\n
func List(l).Map(fn function) List {\n     if l == emptyList {\n         return emptyList\n     }\n\n     return List{Head<-fn(l.Head),Tail<-l.Tail.Map(fn)}\n}<\/code><\/pre>\n\n\n\n
Now let’s code it in Go. <\/p>\n\n\n\n
Test definition<\/p>\n\n\n\n
We will start by defining a code process for our list. We know that we will create a List<\/em> structure witch will contained a Head<\/em> of type interface{}<\/em> (interface <\/em>is a neutral type in Go) and the Tail<\/em> will contained a recursive call to List<\/em> type. For this structure, we wish to define an Empty<\/em> value and an asserter for emptiness. We also wish the constructor of list type to provide an Empty<\/em> list. A first test would then be: 
– When I create a new list
– I expect it to be an Empty list<\/em><\/p>\n\n\n\n
func TestNewList<\/em>(t *testing.T) {\n   Convey(\"When I create a list\", t, func<\/em>() {\n      newList := list.New()\n      Convey(\"I expect it to be empty\", func<\/em>() {\n         So(newList.Empty(), ShouldBeTrue)\n      })\n   })\n}<\/code><\/pre>\n\n\n\n
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<\/em> 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<\/em>

– 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<\/em><\/p>\n\n\n\n
Convey(\"Given I have \", t, func<\/em>() {\n   Convey(\"an Empty list\", func<\/em>() {\n      l := list.New()\n      Convey(\"When I add an element X\", func<\/em>() {\n         newL := l.Prepend(\"X\")\n\n         So(newL.Empty(), ShouldBeFalse)\n         So(newL.Head, ShouldEqual, \"X\")\n         So(newL.Queue.Empty(), ShouldBeTrue)\n      })\n   })\n\n   Convey(\"a list\", func<\/em>() {\n      l := list.New().Prepend(\"X\").Prepend(\"Y\").Prepend(\"Z\")\n      Convey(\"When I add an element X\", func<\/em>() {\n         newL := l.Prepend(\"A\")\n\n         So(newL.Empty(), ShouldBeFalse)\n         So(newL.Head, ShouldEqual, \"A\")\n         So(*newL.Queue, ShouldResemble, l)\n      })\n   })\n})<\/code><\/pre>\n\n\n\n
Then we can define test protocol for Pop<\/em>:
– Given an Empty list<\/em> L<\/em>
– L.Pop() should return nil, EmptyList<\/em>

– Given a [3,4,5] list L<\/em> 
– L.Pop() should return 3, [4,5] as H, L2<\/em>
– L2.Pop() should return 4, [5]<\/em><\/p>\n\n\n\n
Convey(\"Given\", t, func<\/em>() {\n   Convey(\"an Empty list\", func<\/em>() {\n      l := list.New()\n      h, q := l.Pop()\n      So(h, ShouldBeNil)\n      So(q.Empty(), ShouldBeTrue)\n   })\n\n   Convey(\"a known list\", func<\/em>() {\n      l := list.New().Prepend(5).Prepend(4)\n      l2 := l.Prepend(3)\n      h, q := l2.Pop()\n      So(h, ShouldEqual, 3)\n      So(q, ShouldResemble, l)\n      h2, _ := q.Pop()\n      So(h2, ShouldEqual, 4)\n   })\n})<\/code><\/pre>\n\n\n\n
Now, we should ensure Map<\/em> function will behave. 
– Given an Empty List<\/em> L<\/em>
– L.Map(func(e interface{}) {return e}) should return Empty List<\/em>

– Given a single element list L = [“hello”]<\/em>
– And a function addWorld witch add ” world!” to string interface<\/em>
– When I call L.Map(addWorld)<\/em>
– Then I should have [“hello world!”] list<\/em>

– Given a  list L = [“hello”, “my”, “new”]<\/em>
– And a function addWorld witch add ” world!” to string interface<\/em>
– When I call L.Map(addWorld)<\/em>
– Then I should have [“hello world!”, “my world!”, “new world!”] list<\/em><\/p>\n\n\n\n
func TestList_Map<\/em>(t *testing.T) {\n   Convey(\"Given \", t, func<\/em>() {\n      Convey(\"an Empty list\", func<\/em>() {\n         l := list.New()\n         Convey(\"when I apply Map function\", func<\/em>() {\n            newL := l.Map(func<\/em>(e interface<\/em>{}) interface<\/em>{} { return <\/em>e })\n            So(newL.Empty(), ShouldBeTrue)\n         })\n      })\n\n      l := list.New()\n      addWorld := func<\/em>(e interface<\/em>{}) interface<\/em>{} { return <\/em>e.(string) + \" world!\" }\n\n      Convey(\"a single element list\", func<\/em>() {\n         l = l.Prepend(\"hello\")\n         expectedL := list.New().Prepend(\"hello world!\")\n         Convey(\"when I apply Map function\", func<\/em>() {\n            newL := l.Map(addWorld)\n            So(*newL, ShouldResemble, expectedL)\n         })\n      })\n      Convey(\"a  list\", func<\/em>() {\n         l = l.Prepend(\"new\").Prepend(\"my\").Prepend(\"hello\")\n         expectedL := list.New().Prepend(\"new world!\").Prepend(\"my world!\").Prepend(\"hello world!\")\n         Convey(\"when I apply Map function\", func<\/em>() {\n            newL := l.Map(addWorld)\n            So(*newL, ShouldResemble, expectedL)\n         })\n      })\n   })\n}<\/code><\/pre>\n\n\n\n
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.
<\/p>\n\n\n\n
func TestList_BullSort<\/em>(t *testing.T) {\n   Convey(\"Given a list\", t, func<\/em>() {\n      tmpList := list.New().Prepend(1).Prepend(4).Prepend(6).Prepend(9).Prepend(3).Prepend(5).Prepend(2).Prepend(10)\n\n      expectedSorted := list.New().\n         Prepend(1).Prepend(2).Prepend(3).Prepend(4).Prepend(5).\n         Prepend(6).Prepend(9).Prepend(10)\n\n      l := &tmpList\n      comp := func<\/em>(a, b interface<\/em>{}) bool {\n         return <\/em>a.(int) > b.(int)\n      }\n\n      Convey(\"empty or single element, should stay as his\", func() {\n      })\n\n      Convey(\"not sorted, I should be able to sort it\", func<\/em>() {\nfunc TestList_BullSort<\/em>(t *testing.T) {\n   Convey(\"Given a list\", t, func<\/em>() {\n      tmpList := list.New().Prepend(1).Prepend(4).Prepend(6).Prepend(9).Prepend(3).Prepend(5).Prepend(2).Prepend(10)\n\n      expectedSorted := list.New().\n         Prepend(1).Prepend(2).Prepend(3).Prepend(4).Prepend(5).\n         Prepend(6).Prepend(9).Prepend(10)\n\n      l := &tmpList\n      comp := func<\/em>(a, b interface<\/em>{}) bool {\n         return <\/em>a.(int) > b.(int)\n      }\n\n      Convey(\"empty or single element, should stay as his\", func<\/em>() {\n         l := list.New()\n         So(l.BullSort(comp), ShouldResemble, &l)\n\n         l = list.New().Prepend(1)\n         So(l.BullSort(comp), ShouldResemble, &l)\n      })\n\n      Convey(\"not sorted, I should be able to sort it\", func<\/em>() {\n         l = l.BullSort(comp)\n         So(*l, ShouldResemble, expectedSorted)\n      })\n\n      Convey(\"sorted, I should be able to sort it\", func<\/em>() {\n         l = l.BullSort(comp)\n         l = l.BullSort(comp)\n         So(*l, ShouldResemble, expectedSorted)\n      })\n   })\n}<\/code><\/pre>\n\n\n\n
Then, we just have to complete our code until test pass.<\/p>\n\n\n\n
Implementation<\/p>\n\n\n\n
package <\/em>list\n\n\/\/ List represents a simple chained list.\n\/\/ Head provides the element\ntype <\/em>List struct <\/em>{\n   Head interface<\/em>{}\n   Tail *List\n}\n\n\/\/ MapFunc abstracts Map method arguments type\ntype <\/em>MapFunc func<\/em>(element interface<\/em>{}) interface<\/em>{}\n\n\/\/ New initialize an empty list\nfunc New<\/em>() List {\n   return <\/em>List{Tail: nil, Head: nil}\n}\n\n\/\/ Empty asserts list is an empty list.\nfunc <\/em>(l List) Empty<\/em>() bool {\n   return <\/em>l.Head == nil && l.Tail == nil\n}\n\n\/\/ Prepend adds elements to list head.\nfunc <\/em>(l List) Prepend<\/em>(elem interface<\/em>{}) List {\n   return <\/em>List{\n      Head: elem,\n      Tail: &l,\n   }\n}\n\n\/\/ Pop recovers head and queue\nfunc <\/em>(l List) Pop<\/em>() (head interface<\/em>{}, queue List) {\n   if <\/em>l.Empty() {\n      return <\/em>nil, l\n   }\n   return <\/em>l.Head, *l.Tail\n}\n\n\/\/ Map applies a function to each element of a list\nfunc <\/em>(l *List) Map<\/em>(fn MapFunc) *List {\n   if <\/em>l.Empty() {\n      return <\/em>l\n   }\n\n   return <\/em>&List{\n      Head: fn(l.Head),\n      Tail: l.Tail.Map(fn),\n   }\n}\n\n\/\/ AddSorted adds an element to sorted list at the right place.\n\/\/ \/!\\ function will not work correctly on non sorted list.\nfunc <\/em>(l *List) AddSorted<\/em>(e interface<\/em>{}, comp func<\/em>(interface<\/em>{}, interface<\/em>{}) bool) *List {\n   if <\/em>l.Empty() {\n      return <\/em>&List{Head: e, Tail: l}\n   }\n\n   if <\/em>comp(e, l.Head) {\n      return <\/em>&List{Head: e, Tail: l}\n   }\n\n   return <\/em>&List{Head: l.Head, Tail: l.Tail.AddSorted(e, comp)}\n}\n\n\/\/ BullSort sorts a list\nfunc <\/em>(l *List) BullSort<\/em>(comp func<\/em>(interface<\/em>{}, interface<\/em>{}) bool) *List {\n   if <\/em>l.Empty() {\n      return <\/em>l\n   }\n\n   sorted := l.Tail.BullSort(comp)\n\n   return <\/em>sorted.AddSorted(l.Head, comp)\n}<\/code><\/pre>\n\n\n\n
You will find all code written in this article on github: https:\/\/github.com\/switchelven\/data-structure<\/a><\/p>\n\n\n\n
That’s all folks. See you later.<\/p>\n","protected":false},"excerpt":{"rendered":"
Presentation and implementation of List data structure<\/p>","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[4,5],"tags":[17,15,18],"class_list":["post-136","post","type-post","status-publish","format-standard","hentry","category-theorie","category-tutorial","tag-data-structure","tag-go","tag-liste","entry"],"_links":{"self":[{"href":"https:\/\/tutos.switchelven.fr\/fr\/wp-json\/wp\/v2\/posts\/136","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/tutos.switchelven.fr\/fr\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/tutos.switchelven.fr\/fr\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/tutos.switchelven.fr\/fr\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/tutos.switchelven.fr\/fr\/wp-json\/wp\/v2\/comments?post=136"}],"version-history":[{"count":9,"href":"https:\/\/tutos.switchelven.fr\/fr\/wp-json\/wp\/v2\/posts\/136\/revisions"}],"predecessor-version":[{"id":232,"href":"https:\/\/tutos.switchelven.fr\/fr\/wp-json\/wp\/v2\/posts\/136\/revisions\/232"}],"wp:attachment":[{"href":"https:\/\/tutos.switchelven.fr\/fr\/wp-json\/wp\/v2\/media?parent=136"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/tutos.switchelven.fr\/fr\/wp-json\/wp\/v2\/categories?post=136"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/tutos.switchelven.fr\/fr\/wp-json\/wp\/v2\/tags?post=136"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}