Chinmaya's Blog

My Pharo Journey - Implementing a Simple Linked List

Chinmaya Sahu's photo
Chinmaya Sahu
·

6 min read

Table of contents

What's Pharo?

Pharo is a purely object-oriented programming language that comes in a powerful environment that focuses on simplicity and immediate feedback. It is a very powerful tool, that creates an immersive environment, where you can even see the source code of the environment! After all - "Pharo is written in Pharo".

The environment comes with an amazing debugger that lets you create objects and methods on the fly, as and when required. This leads to an easy form of test-driven development. Not to mention, Pharo has a great community with many helpful people, who are always willing to understand your issue and solve your problems!

What's a Linked List?

A linked list is a primitive data structure. It is a linear collection of atomic elements called nodes. It is similar to an array in terms of being sequential, but different because, unlike the array, a Linked List stores elements at different places in memory. On the other hand, an array stores its elements in contiguous memory.

The linked list is composed of nodes, each containing two variables:

  1. Value - the quantity or data that is contained in the nodes.

  2. Next - the pointer to the next node

The next variable in each node is used to obtain the successor of the current node. For the last node, the next variable remains null (or nil in Pharo's case).

Implementation

So, we will be having two classes:

  • LL - This will be the representative of the entire Linked List

  • LLNode - This will be the representative of a node of the Linked List

Linked List

We want to add the following functionalities to our Linked List:

  • A getter and setter method for the head

  • A method that returns the contents of the list

  • A method to append the value at the end of the list

  • A method to show the contents of the list

Linked List Node

We want to add the following fucntionalities to our Linked List node:

  • A getter and setter for the value of the node

  • A getter and setter for the next node pointer of the node

  • A method to print the value of the node

Coding

LLNode

We will begin by making a class called LLNode:

Object subclass: #LLNode
    instanceVariableNames: 'value next'
    classVariableNames: ''
    package: 'MyLinkedList'

Here, we must keep the value of the node and the pointer to the next as an internal variable of the node instance.

We create simple methods for the get and set for next and value and the method for printing the node:

LLNode >> next

    "Returns the node that is after the current one"

    ^next

LLNode >> next: aLLNode

    "Sets the next node"

    next := aLLNode

LLNode >> value

    "Returns the value of the node"

    ^ value

LLNode >> value: anInteger

    "Sets the value of the node"

    value := anInteger

LLNode >> printNode

    "This method is used to print the value of the node in the Transcript"

    Transcript
        show: value asString;
        cr

LL

We will begin by making a class:

Object subclass: #LL
    instanceVariableNames: 'head'
    classVariableNames: ''
    package: 'MyLinkedList'

Here, to describe the list, we only need to store the head internally.

We will make the getter and setter for the head variable:

LL >> head

    "Return the LL node head"

    ^ head

LL >> head: aLLNode

    "Sets the head of the list"

    head := aLLNode

They will come under the accessing protocol.

Next, we will make a method to append values to our linked list:

LL >> appendValue: anInteger

    "This method adds a LLNode to the list with given value"

    | temp newNode |
    temp := head.
    head == nil
        ifTrue: [ head := LLNode new value: anInteger ]
        ifFalse: [ 
            [ temp next isNotNil ] whileTrue: [ temp := temp next ].
            newNode := LLNode new value: anInteger.
            temp next: newNode ]

In this method, we first check if the list is empty (if the head is null), in that case, we can just modify the head and initialize it to a new node. If the head is not null, then the list isn't empty and we can iterate till the end of the list and add a new node.

The next method we want to make is the one to obtain the elements of the list sequentially. We will use the OrderedCollection data structure in Pharo to store this:

LL >> listContent

    "This function is used to return all the values in the linked list"

    | temp retList |
    temp := head.
    retList := OrderedCollection new.
    [ temp value isNotNil ] whileTrue: [ 
        retList add: temp value.
        temp := temp next ].
    ^ retList

Here we initialize a new OrderedCollection, iterate through the list till the end(till the value is null) and simultaneously keep adding the elements to the OrderedCollection.

The last method we want to implement is one to print the contents of the list.

printList

    "This function is used to return all the values in the linked list"

    | temp retStr |
    temp := head.
    retStr := ''.
    [ temp value isNotNil ] whileTrue: [ 
        retStr := (retStr , temp value asString , ' ').
        temp := temp next ].
    ^ retStr

Similarly, here we iterate through the list and keep appending the values to a string.

Protocols

Until this point in time, you should have the panes of the system browser looking like this:

As you can see, the second last pane is the Protocols pane, we want to classify the ones that are not, so click on the as yet unclassified:

To classify these methods, we want to right-click and press Classify Methods:

We want to classify both of these methods under operation. Then we will have something that looks like this:

Now that we have implemented the Linked List Data Structure, it is important to test its functionalities.

A test is written once but run millions of times

Testing

To get started create a new class that inherits the TestCase class:

TestCase subclass: #LLTest
    instanceVariableNames: ''
    classVariableNames: ''
    package: 'MyLinkedList'

In this class, we want to create three methods:

The first one will be to test whether the contents of the list are added in order or not.

LLTest >> testListContent

    | list |
    list := LL new.
    list appendValue: 1;appendValue: 2;appendValue: 3.
    self assert: list listContent equals: #(1 2 3) asOrderedCollection .

We will see something like this in the methods pane:

If we click on the button, if everything is implemented correctly, then it should come as such:

Similarly, we make two more tests. The second test is for checking whether the node is appended properly or not.

LLTest >> testAppendNode

    | temp list |
    list := LL new.

    list
        appendValue: 1;
        appendValue: 2.

    temp := list head.

    [ temp next == nil ] whileFalse: [ temp := temp next ].

    self assert: temp value equals: 2

The third test is to check the initialization of the linked list:

LLTest >> testInitialize

    | list |
    list := LL new.
    list appendValue: 1.
    self assert: list head value equals: 1

If everything has run correctly, we can see the methods pane as such:

If we go back and look at our list content method, we can see our methods pane looking like this:

To simultaneously run all the test cases, we can press the green button of the test case class:

So there it is, a successful implementation of a simple linked list!

I hope you liked the blog! Thanks for reading! Feel Free to leave suggestions in the comments below!

#linkedlistsdata structuresPharo