{"id":136,"date":"2021-02-04T23:05:40","date_gmt":"2021-02-04T22:05:40","guid":{"rendered":"https:\/\/tutos.switchelven.fr\/?p=136"},"modified":"2026-08-16T13:00:28","modified_gmt":"2026-08-16T11:00:28","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\nOur 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\u00a0{\n return l\n }\n \n sorted = l.Tail.Sort()\n return sorted.Add()\n}<\/code><\/pre>\n\n\n\nFinally, 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\nNow 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\nThen 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\nThen 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\nNow, 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\nFinally, 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\nThen, 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\nYou 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