2. List¶
Prerequisite
- Familiar with classes in Lua
- Setup code editor with Lua
Overview¶
A List is a very common data structure that stores values in nodes, where each node contains a value and a pointer to the next node. Unlike arrays (not tables), linked lists can dynamically grow or shrink and do not require contiguous memory. Implement a linked list as a class in Lua to store arbitrary values of any type.
Recall that classes can be created like:
local Box = {}
Box.__index = Box
function Box.new(x) -- static constructor
local self = setmetatable({}, Box)
self.x = x
return self
end
function Box:Get() -- instance method (note ':')
return self.x
end
return Box
Tasks¶
Task 1: List class¶
Create a skeleton List class with the constructor and necessary fields. Add a toString method so that the string representation as shown in the examples below could be returned.
For instance:
Task 2: Append() and Pop()¶
Add Append() and Pop() methods to manipulate the list. Append(x) should append x in a List to the back. Pop() should pop the last value in the list and return it. Also modify the toString() method to correctly display the values in the list.
For instance:
local list = List.new(1)
list:Append(2)
print(list:toString()) -- should print "[1 2]"
local popped = list:Pop()
print(popped) -- should print "2"
print(list:toString()) -- should print "[1]"
Task 3: Length()¶
Add a Length() method to get the length of the instance list.
For instance:
Task 4: Get(i) and Remove(i)¶
Add a Get(i) method to retrieve the List at index i (1-based). The method should traverse and return the List node if it exists, or nil if the index is out of bounds. Add a Remove(i) method to remove only the List at index i and return it.
Hint: consider using two traversal variables
For instance:
local list = List.new(1)
list:Append(2)
list:Append(3)
print(list:Get(2):toString()) -- should print "[2 3]"
print(list:Remove(2):toString()) -- should print "[2]"
print(list:toString()) -- should print "[1 3]"
Solution¶
local List = {}
List.__index = List
-- Constructor: Initialize a node with data and a nil tail
function List.new(data)
local self = setmetatable({}, List)
self.data = data
self.tail = nil
return self
end
-- Add an element with value `x` to the end of the list
function List:append(x)
local curr = self
while curr.tail do
curr = curr.tail
end
curr.tail = List.new(x)
end
-- Pop the last List and return its value
function List:pop()
if not self.tail then
return self.data
end
local curr = self
while curr.tail and curr.tail.tail do
curr = curr.tail
end
local value = curr.tail.data
curr.tail = nil
return value
end
-- Get the List at index `i`
function List:get(i: number)
local curr = self
local j = 1
while j < i and curr.tail do
curr = curr.tail
j = j + 1
end
return j == i and curr or nil
end
-- Remove the List at index `i`
function List:remove(i: number)
local prev = nil
local curr = self
local j = 1
while j < i and curr.tail do
prev = curr
curr = curr.tail
j = j + 1
end
if j == i then
-- for non-head, we stitch the prev to the next tail
-- for head removal edge case (undefined by qn),
-- i choose to cut off the remaining list and let GC clean it up
if prev then
prev.tail = curr.tail
end
curr.tail = nil
return curr
end
return nil
end
-- Get the length of the list
function List:length()
local curr = self.tail
local i = 1
while curr do
i = i + 1
curr = curr.tail
end
return i
end
return List
// This implementation is closer to the CS1101S implementation
public class List {
private int data;
private List tail;
// Constructor
public List(int data) {
this.data = data;
this.tail = null;
}
// Add an element with value x to the end
public void append(int x) {
List curr = this;
while (curr.tail != null) {
curr = curr.tail;
}
curr.tail = new List(x);
}
// Pop the last node and return the value
public int pop() {
if (this.tail == null) {
return this.data;
}
List curr = this;
while (curr.tail != null && curr.tail.tail != null) {
curr = curr.tail;
}
int res = curr.tail.data;
curr.tail = null;
return res;
}
// Get the List at index i
public List get(int i) {
List curr = this;
int j = 0;
while (j < i && curr.tail != null) {
curr = curr.tail;
j++;
}
if (j == i) {
return curr;
}
return null;
}
// Remove the List at index i
public List remove(int i) {
List prev = null;
List curr = this;
int j = 0;
while (j < i && curr.tail != null) {
prev = curr;
curr = curr.tail;
j++;
}
if (j == i) {
// for non-head, we stitch the prev to the next tail
// for head removal edge case (undefined by qn),
// i choose to cut off the remaining list and let GC clean it up
if (prev != null) {
prev.tail = curr.tail;
}
curr.tail = null;
return curr;
}
return null;
}
// Get the length of the list
public int length() {
int i = 1;
// you can use for loops like this too, but rest of the code
// uses while loops for clarity
for (List curr = this.tail; curr != null; curr = curr.tail, i++);
return i;
}
// Helper function
public void print() {
List curr = this;
while (curr != null) {
System.out.print(curr.data + " ");
curr = curr.tail;
}
System.out.print("\n");
}
}
Extra¶
Consider what else we can do with lists? Is there a point of implementing lists when we already have tables? How could you use tables to write a much terser linked list? How could we use lists in game development?