We need an efficient structure to store a large number of entries that we can quickly traverse. The mapping data type in solidity is wonderful for storing information, but very hard to look through if you don’t already know the index of each item. With a linked list you store an index to the next piece of data in the current piece of data like a chain. To make writes our most efficient operation, we want to add items to the front of the list by keeping track of a head index. When we want to add a new element we put the existing head index in as the new element’s next index and then set the head to the new element. This operation costs the same computational amount for a list of any size. When we want to look through the data, we start at the head index and follow the trail of next indexes.

Let’s create a contract called LinkedList that stores a list of Objects that are all linked together. An Object is a struct data type that holds an index to the next object along with a name and a number. For demonstration purposes, let’s say this contract is meant to hold voting information from small, fictitious districts where name is a candidate’s name and number is the number of votes that candidate received in the district.

``````pragma solidity ^0.4.11;

uint public length = 0;//also used as nonce

struct Object{
bytes32 next;
uint number;
bytes32 name;
}

mapping (bytes32 => Object) public objects;

function addEntry(uint _number,bytes32 _name) public returns (bool){
bytes32 id = sha3(object.number,object.name,now,length);
objects[id] = object;
length = length+1;
}

function getEntry(bytes32 _id) public returns (bytes32,uint,bytes32){
return (objects[_id].next,objects[_id].number,objects[_id].name);
}

//------------------ totalling stuff to explore list mechanics

function total() public constant returns (uint) {
uint totalCount = 0;
while( current != 0 ){
totalCount = totalCount + objects[current].number;
current = objects[current].next;
}
}

function setTotal() public returns (bool) {
writtenTotal = total();
return true;
}

function resetTotal() public returns (bool) {
writtenTotal = 0;
return true;
}

uint public writtenTotal;

}

``````

Again, we will skip the compile, deploy, and scripting mechanics assuming readers have followed along from previous explorations.

``````node compile LinkedList

0xFD400Ff1b9f23b105386350309C0616A50c969bE
``````

Then, let’s populate the contract with a bunch of transactions similar to:

``````node contract addEntry LinkedList null 93 "Bram"
``````

Let’s have a bunch of districts report in with their results:

``````node contract addEntry LinkedList null 26 "Hal"
``````

Then, we can run our getTotal() function to count the total votes:

``````node contract getTotal LinkedList

TOTAL:370
``````

It is free for us to run the getTotal off-chain, but if we need to change the state of the contract we will have to pay for it in gas. Let’s explore the gas costs a little more to figure out what we are dealing with.

Let’s run the setTotal() function which will run the getTotal() just like we did off-chain, but then it will write it to the writtenTotal uint. Because there is a change of state, every single contract in the network will have to iterate through our linked-list and deterministically reach the same total. This will cost us some gas:

``````node contract setTotal LinkedList
``````

(Transaction on etherscan.io)

To run through the list, keep track of a total, and eventually write that total to state, it cost 0.001034044 ether.

(See all 349 operations on etherscan.io)

Now, if we change the same state without traversing the list using the resetTotal() function, let’s see what that costs:

``````node contract resetTotal LinkedList
``````

(Transaction on etherscan.io)

Wow, that was cheap, only 0.000292974 ether. So maybe we can subtract those two numbers and probably figure out how much it costs to traverse the list?

In USD, assuming ETH is about \$300, paying 22 gwei in gas, it’s about \$0.09 to set the value of our uint and about \$0.22 to traverse our list of 10 entries keeping a running total. Looking back at adding an entry, at the same rate, it cost about \$0.63. Keeping separation of concerns in mind, let’s create a second contract that will interact with the LinkedList contract instead of writing the functionality directly into the LinkedList contract. This contract will be called the Teller and will count the votes once a quorum is reached.

``````pragma solidity ^0.4.11;

contract Teller {

uint16 public quorum = 400;
bytes32 public winningName;

enum States {
WaitingForQuorum,
ElectionFinished
}

States public state = States.WaitingForQuorum;

function Teller(){ }

bytes32 public currentPointer;
mapping (bytes32 => uint) public totals;
uint public counted=0;

if( state == States.WaitingForQuorum ){
return true;
}else if( state == States.CountingVotes ){
if( currentPointer==0 ){
}
uint8 limitPerTurn = 4;
while ( limitPerTurn-- > 0 && currentPointer!=0 ){
uint thisNumber;
bytes32 thisName;
totals[thisName] += thisNumber;
winningName=thisName;
}
counted++;
}
if( currentPointer==0 ){
state = States.ElectionFinished;
return true;
}else{
return false;
}
}else{
revert();
}
}
}

struct Object{ bytes32 next;uint number;bytes32 name;}
mapping (bytes32 => Object) public objects;
function total() public constant returns (uint) {}
function getEntry(bytes32 _id) public returns (bytes32,uint,bytes32){}
}

``````

Using the enum data type we can code the Teller to perform like a state machine. Notice how the countVotes() function changes the state as it detects new conditions. The most important concept here is the limitPerTurn. Because of gas limits (see halting problem), we won’t be able to traverse the entire list in one transaction. What we have to do is move through part of it and then keep track of the running totals between transactions. In production, we will use the msg.gas variable, but for demonstration purposes, we will just count four at a time.

``````node compile Teller
node deploy Teller

0x3c67a0e63a967810fcC5e48F9a94c6D561D9a7cd
``````

The current getTotal() of the LinkedList contract is returning 370. So if we run the countVotes() function against the LinkedList contract address, the Teller should stay in state 0:

``````node contract countVotes Teller null 0xFD400Ff1b9f23b105386350309C0616A50c969bE
node contract getState Teller

STATE:0
``````

Let’s throw in one last vote count to push the total past the require quorum of 400:

``````node contract addEntry LinkedList null 32 "Bram"

TOTAL:402
``````

Now, when we trigger the countVotes() function, the state should change to 1 which represents the state of CountingVotes:

``````node contract countVotes Teller null 0xFD400Ff1b9f23b105386350309C0616A50c969bE
node contract getState Teller

STATE:1
``````

Let’s inspect a few variables in the Teller contract before we start tallying votes:

``````node contract getCounted Teller
COUNTED:0

node contract getCurrentPointer Teller
CURRENTPOINTER:0x0000000000000000000000000000000000000000000000000000000000000000
``````

Now let’s fire off the first round of vote counting which should total up the first four votes:

``````node contract countVotes Teller null 0xFD400Ff1b9f23b105386350309C0616A50c969bE

node contract getCounted Teller
COUNTED:4

node contract getCurrentPointer Teller
CURRENTPOINTER:0xa286649c24c2fe84cceb42001867f0d66be3fcc1e9612f9974ed74d6fb86375f
``````

We can also see who is in the lead after the first four votes are totaled but since the state is still CountingVotes, we know the election isn’t finished:

``````node contract getWinningName Teller
WINNINGNAME:Hal

node contract getState Teller
STATE:1
``````

Let’s finish the election off by running the countVotes() function until the state changes to 2 (ElectionFinished):

``````node contract countVotes Teller null 0xFD400Ff1b9f23b105386350309C0616A50c969bE
node contract countVotes Teller null 0xFD400Ff1b9f23b105386350309C0616A50c969bE

node contract getState Teller
STATE:2
``````

Now we can be confident that we have selected our true winner and our election is finished:

``````node contract getWinningName Teller
WINNINGNAME:Hal