 # JaeHyoLee's solution

## to Linked List in the Lua Track

Published at Jul 13 2018 · 0 comments
Instructions
Test suite
Solution

Like an array, a linked list is a simple linear data structure. Several common data types can be implemented using linked lists, like queues, stacks, and associative arrays.

A linked list is a collection of data elements called nodes. In a singly linked list each node holds a value and a link to the next node. In a doubly linked list each node also holds a link to the previous node.

You will write an implementation of a doubly linked list. Implement a Node to hold a value and pointers to the next and previous nodes. Then implement a List which holds references to the first and last node and offers an array-like interface for adding and removing items:

• `push` (insert value at back);
• `pop` (remove value at back);
• `shift` (remove value at front).
• `unshift` (insert value at front);

To keep your implementation simple, the tests will not cover error conditions. Specifically: `pop` or `shift` will never be called on an empty list.

## Running the tests

To run the tests, run the command `busted` from within the exercise directory.

## Further information

For more detailed information about the Lua track, including how to get help if you're having trouble, please visit the exercism.io Lua language page.

## Source

Classic computer science topic

## Submitting Incomplete Solutions

It's possible to submit an incomplete solution so you can see how others have completed the exercise.

``````local LinkedList = require('linked-list')

it('should be able to pop pushed elements', function()
list:push(10)
list:push(20)
assert.equal(20, list:pop())
assert.equal(10, list:pop())
end)

it('should be able to shift pushed elements', function()
list:push(10)
list:push(20)
assert.equal(10, list:shift())
assert.equal(20, list:shift())
end)

it('should be able to shift unshifted elements', function()
list:unshift(10)
list:unshift(20)
assert.equal(20, list:shift())
assert.equal(10, list:shift())
end)

it('should be able to pop unshifted elements', function()
list:unshift(10)
list:unshift(20)
assert.equal(10, list:pop())
assert.equal(20, list:pop())
end)

it('should be able to count its elements', function()
assert.equal(0, list:count())
list:push(10)
assert.equal(1, list:count())
list:push(20)
assert.equal(2, list:count())

end)

it('should count correctly after a shift', function()
list:push(10)
list:push(20)
list:shift()
assert.equal(1, list:count())
end)

it('should count correctly after a pop', function()
list:push(10)
list:push(20)
list:pop()
assert.equal(1, list:count())
end)

it('should be able to delete from the beginning of the list', function()
list:push(10)
list:push(20)
list:push(30)
list:delete(30)
assert.equal(2, list:count())
assert.equal(20, list:pop())
assert.equal(10, list:shift())
end)

it('should be able to delete from the middle of the list', function()
list:push(10)
list:push(20)
list:push(30)
list:delete(20)
assert.equal(2, list:count())
assert.equal(30, list:pop())
assert.equal(10, list:shift())
end)

it('should be able to delete from the end of the list', function()
list:push(10)
list:push(20)
list:push(30)
list:delete(10)
assert.equal(2, list:count())
assert.equal(30, list:pop())
assert.equal(20, list:shift())
end)

it('should delete all elements with the matching value', function()
list:push(10)
list:push(20)
list:push(20)
list:push(30)
list:delete(20)
assert.equal(2, list:count())
assert.equal(30, list:pop())
assert.equal(10, list:shift())
end)

it('should be able to delete the only element', function()
list:push(10)
list:delete(10)
assert.equal(0, list:count())
end)
end)``````
``````local LinkedList = {}

local node = {
value = n,
prev = self.list.tail,
next = nil }
if self.list.count == 0 then
self.list.tail = node
else
self.list.tail.next = node
self.list.tail = node
end
self.list.count = self.list.count + 1
end

if self.list.count >0 then
local value = self.list.tail.value
if self.list.tail.prev ~= nil then
self.list.tail.prev.next = nil
self.list.tail = self.list.tail.prev
end
self.list.count = self.list.count - 1
return value
end
end

local node = {
value = n,
prev = nil,
if self.list.count == 0 then
self.list.tail = node
else
end
self.list.count = self.list.count + 1
end

if self.list.count > 0 then
end
self.list.count = self.list.count - 1
return value
end
end

return self.list.count
end

while node ~= nil do
if node.value == n then
if node.prev ~= nil then node.prev.next = node.next
if node.next ~= nil then node.next.prev = node.prev
else self.list.tail = node.prev end
self.list.count = self.list.count - 1
end
node = node.next
end
end

return function()
self.list = {head = nil, tail = nil, count = 0}
return self
end``````