LinkedList Implementation
Java
LinkedList.java
package collections;
/**
* This class represents a list implemented over singly-linked nodes.
* invariants:
* <ul>
* <li>No loops: for every node {@code n} reachable from {@code head}, {@code n} cannot be reached by {@code Node#getNext()} from {@code n.getNext()}.</li>
* <li>The size of the list must be the same as the nodes reachable from {@code head}.</li>
* </ul>
*/
public class LinkedList<T> {
/* (non-javadoc)
* The root node of this list.
*/
private Node<T> head;
/* (non-javadoc)
* The amount of elements in this list.
*/
private int size;
/**
* Constructs a new empty list.
*/
public LinkedList()
{
head = null;
size = 0;
}
/**
* Constructs a new list from another, the elements of the other list will be added to
* this list.
* preconditions:
* <ul>
* <li>the other list cannot be {@code null}</li>
* </ul>
* @param from the other list from where to construct this
*/
public LinkedList(LinkedList<T> from)
{
//TODO: implement and remove following statement
if(from == null) {
throw new IllegalArgumentException("the other list cannot be null");
}
Node<T> current = from.head;
while(current != null) {
add(current.getValue());
current = current.getNext();
}
if(!repOk()) {
throw new IllegalStateException("The class invariants are not satisfied!");
}
}
/**
* Adds a value to the end of this list.
* //TODO: add pre and post conditions (value can be null), implement pre/post condition checking using exceptions.
* @param value the value to add
*/
public void add(T value)
{
int originalSize = size; //used to check post condition
if (head == null) {
head = new Node<T>(value);
} else {
Node<T> current = head;
while (current.hasNext()) {
current = current.getNext();
}
current.setNext(new Node<T>(value));
}
size++;
if(size != originalSize + 1){
throw new IllegalStateException("error, size didn't increase by 1!");
}
T lastValue = at(size - 1);
if ((value == null && lastValue != null) || (value != null && !value.equals(lastValue))) {
throw new IllegalStateException("The new value is not added in the last");
}
if(!repOk()) {
throw new IllegalStateException("The class invariants are not satisfied!");
}
}
/**
* Adds a value to the end of this list.
* //TODO: add pre and post conditions (value can be null), implement pre/post condition checking using exceptions.
* @param value the value to add
*/
public void append(T value)
{
//TODO: implement and remove following statement
int originalSize = size; //used to check post condition
if (head == null) {
head = new Node<T>(value);
} else {
Node<T> current = head;
while (current.hasNext()) {
current = current.getNext();
}
current.setNext(new Node<T>(value));
}
size++;
if(size != originalSize + 1){
throw new IllegalStateException("error, size didn't increase by 1!");
}
T lastValue = at(size - 1);
if ((value == null && lastValue != null) || (value != null && !value.equals(lastValue))) {
throw new IllegalStateException("The new value is not added in the last");
}
if(!repOk()) {
throw new IllegalStateException("The class invariants are not satisfied!");
}
}
/**
* Adds a value to the beginning of this list, shift all existing elements one place to the right.
* //TODO: add pre and post conditions (value can be null), implement pre/post condition checking using exceptions.
* @param value the value to add
*/
public void prepend(T value)
{
//TODO: implement and remove following statement
int originalSize = size;
Node<T> oldHead = head;
Node<T> newNode = new Node<T>(value);
newNode.setNext(head);
head = newNode;
size++;
if(size != originalSize + 1){
throw new IllegalStateException("error, size didn't increase by 1!");
}
if(head == null || !at(0).equals(value)) {
throw new IllegalStateException("The new value should be the first element of the list");
}
if(originalSize > 0 && head.getNext() != oldHead) {
throw new IllegalStateException("Existing elements were not shifted");
}
if(!repOk()) {
throw new IllegalStateException("The class invariants are not satisfied!");
}
}
/**
* Adds a value at a specific position shifting all values
* starting from that position one place to the right.
* //TODO: add pre and post conditions (value can be null), implement pre/post condition checking using exceptions.
* @param value the value to add
* @param at the index at which to add.
* <hr>
* <b>Calling with an index greater or equal to {@code LinkedList#size()} is equivalent to calling {@code LinkedList#add(T)}.</b>
*/
public void addAt(T value, int at)
{
//TODO: implement and remove following statement
if(at < 0) {
throw new IllegalArgumentException("at is negative or out of bound!");
}
int originalSize = size;//used to check post condition
if(at == 0) {
prepend(value);
}
else if(at >= size) {
append(value);
}
else {
Node<T> current = head;
for(int i = 0; i < at - 1; i++) {
current = current.getNext();
}
current.setNext(new Node<T>(value, current.getNext()));
size++;
}
if(size != originalSize + 1) {
throw new IllegalStateException("error, size didn't increase by 1!");
}
T atValue = at(at);
if ((value == null && atValue != null) || (value != null && !value.equals(atValue))) {
throw new IllegalStateException("The new value is not added in the at");
}
if(!repOk()) {
throw new IllegalStateException("The class invariants are not satisfied!");
}
}
/**
* Returns the element at a given position.
* //TODO: add pre and post conditions, implement precondition checking using exceptions.
* @param i the index of the element to retrieve
* @return the element at position {@code i}.
*/
public T at(int i)
{
if(i < 0 || i >= size) {
throw new IllegalArgumentException("i is negative or out of bound!");
}
Node<T> current = head;
for (int j = 0; j < i; j++) {
current = current.getNext();
}
return current.getValue();
}
/**
* Returns the first element of this list.
* //TODO: add pre and post conditions, implement precondition checking using exceptions.
* @return the first element of this list.
* <hr>
* <b>This method is equivalent to {@code at(0)}.</b>
*/
public T first()
{
//TODO: implement and remove following statement
if(size == 0) {
throw new IllegalStateException("List is empty");
}
return at(0);
}
/**
* Returns the last element of this list.
* //TODO: add pre and post conditions, implement precondition checking using exceptions.
* @return the first element of this list.
* <hr>
* <b>This method is equivalent to {@code at(size() - 1)}.</b>
*/
public T last()
{
//TODO: implement and remove following statement
if(size == 0) {
throw new IllegalStateException("List is empty");
}
return at(size - 1);
}
/**
* Removes the value at a specific position shifting all values
* starting from the next position one place to the left.
* //TODO: add pre and post conditions (value can be null), implement pre/post condition checking using exceptions.
* @param i the index of the element to remove.
*/
public void removeAt(int at)
{
if(at < 0 || at >= size) {
throw new IllegalArgumentException("at is negative or out of bound!");
}
int originalSize = size;
if (at == 0) {
head = head.getNext();
} else {
Node<T> prev = head;
for (int i = 0; i < at - 1; i++) {
prev = prev.getNext();
}
Node<T> nodeAfterDeleted = prev.getNext().getNext();
prev.setNext(nodeAfterDeleted);
}
size--;
if(size != originalSize - 1) {
throw new IllegalStateException("error, size didn't decrease by 1!");
}
if(!repOk()) {
throw new IllegalStateException("The class invariants are not satisfied!");
}
}
/**
* Removes the first value of the list shifting all values from position {@code 1}
* one place to the left.
* //TODO: add pre and post conditions (value can be null), implement pre/post condition checking using exceptions.
*/
public void removeFirst()
{
//TODO: implement and remove following statement
if(size == 0) {
throw new IllegalStateException("List is empty");
}
int originalSize = size;
removeAt(0);
if (size != originalSize - 1) {
throw new IllegalStateException("error, size didn't decrease by 1!");
}
if (!repOk()) {
throw new IllegalStateException("The class invariants are not satisfied!");
}
}
/**
* Removes the last value of the list.
* //TODO: add pre and post conditions (value can be null), implement pre/post condition checking using exceptions.
*/
public void removeLast()
{
//TODO: implement and remove following statement
if(size == 0) {
throw new IllegalStateException("List is empty");
}
int originalSize = size;
removeAt(size - 1);
if (size != originalSize - 1) {
throw new IllegalStateException("error, size didn't decrease by 1!");
}
if (!repOk()) {
throw new IllegalStateException("The class invariants are not satisfied!");
}
}
/**
* Checks whether an element is contained in this list.
* @param value the the value to search
*/
public boolean contains(T value)
{
//TODO: implement and remove following statement
Node<T> current = head;
while (current != null) {
T currentValue = current.getValue();
if (currentValue == null && value == null) {
return true;
}
else if (currentValue != null && value != null && currentValue.equals(value)) {
return true;
}
current = current.getNext();
}
return false;
}
/**
* @return the size of this list
*/
public int size()
{
return size;
}
/**
* Compares this list against another object.
* @param other the object to compare with
* @return {@code true} iff {@code other} represents the same list as this one
*/
@Override
public boolean equals(Object other)
{
//TODO: implement any previous code
if (other == null){
return false;
}
if (!(other instanceof LinkedList<?>)) {
return false;
}
LinkedList<?> otherAsLL = (LinkedList<?>) other;
//hint: for null values you don't care about types
//hint: compare elements of this list, against elements of the other list
//TODO: implement and remove following statement
if (this.size() != otherAsLL.size()) {
return false;
}
Node<T> currentThis = head;
Node<?> currentOther = otherAsLL.head;
while (currentThis != null && currentOther != null) {
T thisValue = currentThis.getValue();
Object otherValue = currentOther.getValue();
if (thisValue == null && otherValue == null) {
}
else if (thisValue != null && otherValue != null && thisValue.equals(otherValue)) {
}
else {
return false;
}
currentThis = currentThis.getNext();
currentOther = currentOther.getNext();
}
return true;
}
/**
* Returns a string representation of this list with the format {@code [<elements>]},
* where {@code <elements>} is a comma separated list of the string representation of
* each element on this list.
* @return a string representation of this list
*/
@Override
public String toString()
{
String result = "[";
Node<T> current = head;
while (current != null) {
result += (current.getValue() == null ? "null" : current.getValue());
if (current.hasNext()) {
result += ", ";
}
current = current.getNext();
}
result += "]";
return result;
}
/**
* Checks the invariant of this class
* @return {@code true} iff this object complies/satisfies all class invariants
*/
public boolean repOk()
{
//TODO: implement and remove following statement
int countedSize = 0;
Node<T> current = head;
while (current != null && countedSize <= size) {
// Check whether current appears in the list before we reach size
int nodesChecked = 0;
Node<T> checker = head;
while (checker != current && nodesChecked < countedSize) {
checker = checker.getNext();
nodesChecked++;
}
// If we found current before the expected position, that's a loop
if (checker == current && nodesChecked < countedSize) {
return false;
}
current = current.getNext();
countedSize++;
}
if(countedSize != size) {
return false;
}
return true;
}
}
Node.java
package collections;
/* (non-javadoc)
* This class represents a singly linked node with an associated value.
* @version 0.1
*/
class Node<T> {
private T value;
private Node<T> next;
/* (non-javadoc)
* Constructs a new node with a {@code null} value
* and no next ({@code null} as next).
*/
public Node()
{
value = null;
next = null;
}
/* (non-javadoc)
* Constructs a new node with a specific value
* and no next ({@code null} as next).
* @param value the value for this node
*/
public Node(T value)
{
this.value = value;
next = null;
}
/* (non-javadoc)
* Constructs a new node with a specific value
* and a specific next node.
* @param value the value for this node
* @param next the next node
*/
public Node(T value, Node<T> next)
{
this.value = value;
this.next = next;
}
/* (non-javadoc)
* @return the value associated to this node.
*/
public T getValue()
{
return value;
}
/* (non-javadoc)
* Changes the value associated to this node.
* param value the new value for this node
*/
public void setValue(T value)
{
this.value = value;
}
/* (non-javadoc)
* @return the next node.
*/
public Node<T> getNext()
{
return next;
}
/* (non-javadoc)
* @return {@code true} iff {@code getNext() != null}.
*/
public boolean hasNext()
{
return next != null;
}
/* (non-javadoc)
* Changes the next node.
* param next the new next node
*/
public void setNext(Node<T> next)
{
this.next = next;
}
}
Python
Node.py
class Node:
def __init__(self, value=None, next=None):
self.value = value
self.next = next
def getValue(self):
return self.value
def setValue(self, value):
self.value = value
def getNext(self):
return self.next
def hasNext(self):
return self.next is not None
def setNext(self, next):
self.next = next
LinkedList.py
class LinkedList:
def __init__(self, from_list=None):
self.head = None
self.size = 0
if from_list is not None:
if from_list is None:
raise ValueError("the other list cannot be null")
current = from_list.head
while current is not None:
self.add(current.getValue())
current = current.getNext()
def add(self, value):
if self.head is None:
self.head = Node(value)
else:
current = self.head
while current.hasNext():
current = current.getNext()
current.setNext(Node(value))
self.size += 1
def append(self, value):
if self.head is None:
self.head = Node(value)
else:
current = self.head
while current.hasNext():
current = current.getNext()
current.setNext(Node(value))
self.size += 1
def prepend(self, value):
new_node = Node(value)
new_node.setNext(self.head)
self.head = new_node
self.size += 1
def addAt(self, value, at):
if at < 0:
raise ValueError("at is negative or out of bound!")
if at == 0:
self.prepend(value)
elif at >= self.size:
self.append(value)
else:
current = self.head
for i in range(at - 1):
current = current.getNext()
current.setNext(Node(value, current.getNext()))
self.size += 1
def at(self, i):
if i < 0 or i >= self.size:
raise ValueError("i is negative or out of bound!")
current = self.head
for j in range(i):
current = current.getNext()
return current.getValue()
def first(self):
if self.size == 0:
raise ValueError("List is empty")
return self.at(0)
def last(self):
if self.size == 0:
raise ValueError("List is empty")
return self.at(self.size - 1)
def removeAt(self, at):
if at < 0 or at >= self.size:
raise ValueError("at is negative or out of bound!")
if at == 0:
self.head = self.head.getNext()
else:
prev = self.head
for i in range(at - 1):
prev = prev.getNext()
prev.setNext(prev.getNext().getNext())
self.size -= 1
def removeFirst(self):
if self.size == 0:
raise ValueError("List is empty")
self.removeAt(0)
def removeLast(self):
if self.size == 0:
raise ValueError("List is empty")
self.removeAt(self.size - 1)
def contains(self, value):
current = self.head
while current is not None:
current_value = current.getValue()
if current_value == value:
return True
current = current.getNext()
return False
def size(self):
return self.size
def __str__(self):
result = "["
current = self.head
while current is not None:
result += str(current.getValue()) if current.getValue() is not None else "null"
if current.hasNext():
result += ", "
current = current.getNext()
result += "]"
return result
C++
Node.h
#ifndef NODE_H
#define NODE_H
template <typename T>
class Node {
private:
T value;
Node<T>* next;
public:
Node() : value(), next(nullptr) {}
Node(T val) : value(val), next(nullptr) {}
Node(T val, Node<T>* nxt) : value(val), next(nxt) {}
T getValue() {
return value;
}
void setValue(T val) {
value = val;
}
Node<T>* getNext() {
return next;
}
bool hasNext() {
return next != nullptr;
}
void setNext(Node<T>* nxt) {
next = nxt;
}
};
#endif
LinkedList.h
#ifndef LINKEDLIST_H
#define LINKEDLIST_H
#include "Node.h"
#include <string>
#include <stdexcept>
template <typename T>
class LinkedList {
private:
Node<T>* head;
int size;
void clear() {
while (head != nullptr) {
Node<T>* temp = head;
head = head->getNext();
delete temp;
}
size = 0;
}
public:
LinkedList() : head(nullptr), size(0) {}
LinkedList(LinkedList<T>* from) : head(nullptr), size(0) {
if (from == nullptr) {
throw std::invalid_argument("the other list cannot be null");
}
Node<T>* current = from->head;
while (current != nullptr) {
add(current->getValue());
current = current->getNext();
}
}
~LinkedList() {
clear();
}
// Copy constructor
LinkedList(const LinkedList<T>& other) : head(nullptr), size(0) {
Node<T>* current = other.head;
while (current != nullptr) {
add(current->getValue());
current = current->getNext();
}
}
// Assignment operator
LinkedList<T>& operator=(const LinkedList<T>& other) {
if (this != &other) {
clear();
Node<T>* current = other.head;
while (current != nullptr) {
add(current->getValue());
current = current->getNext();
}
}
return *this;
}
void add(T value) {
if (head == nullptr) {
head = new Node<T>(value);
} else {
Node<T>* current = head;
while (current->hasNext()) {
current = current->getNext();
}
current->setNext(new Node<T>(value));
}
size++;
}
void append(T value) {
if (head == nullptr) {
head = new Node<T>(value);
} else {
Node<T>* current = head;
while (current->hasNext()) {
current = current->getNext();
}
current->setNext(new Node<T>(value));
}
size++;
}
void prepend(T value) {
Node<T>* newNode = new Node<T>(value);
newNode->setNext(head);
head = newNode;
size++;
}
void addAt(T value, int at) {
if (at < 0) {
throw std::invalid_argument("at is negative or out of bound!");
}
if (at == 0) {
prepend(value);
} else if (at >= size) {
append(value);
} else {
Node<T>* current = head;
for (int i = 0; i < at - 1; i++) {
current = current->getNext();
}
current->setNext(new Node<T>(value, current->getNext()));
size++;
}
}
T at(int i) {
if (i < 0 || i >= size) {
throw std::invalid_argument("i is negative or out of bound!");
}
Node<T>* current = head;
for (int j = 0; j < i; j++) {
current = current->getNext();
}
return current->getValue();
}
T first() {
if (size == 0) {
throw std::runtime_error("List is empty");
}
return at(0);
}
T last() {
if (size == 0) {
throw std::runtime_error("List is empty");
}
return at(size - 1);
}
void removeAt(int at) {
if (at < 0 || at >= size) {
throw std::invalid_argument("at is negative or out of bound!");
}
if (at == 0) {
Node<T>* temp = head;
head = head->getNext();
delete temp;
} else {
Node<T>* prev = head;
for (int i = 0; i < at - 1; i++) {
prev = prev->getNext();
}
Node<T>* toDelete = prev->getNext();
prev->setNext(toDelete->getNext());
delete toDelete;
}
size--;
}
void removeFirst() {
if (size == 0) {
throw std::runtime_error("List is empty");
}
removeAt(0);
}
void removeLast() {
if (size == 0) {
throw std::runtime_error("List is empty");
}
removeAt(size - 1);
}
bool contains(T value) {
Node<T>* current = head;
while (current != nullptr) {
if (current->getValue() == value) {
return true;
}
current = current->getNext();
}
return false;
}
int getSize() {
return size;
}
std::string toString() {
std::string result = "[";
Node<T>* current = head;
while (current != nullptr) {
// Assuming T has operator<< defined; otherwise, specialize for types
result += std::to_string(current->getValue());
if (current->hasNext()) {
result += ", ";
}
current = current->getNext();
}
result += "]";
return result;
}
};
#endif
Implement List using a DoublyLinkedList and an ArrayList
// DoublyNode.java
package collections;
/**
* This class represents a doubly linked node with an associated value.
*/
class DoublyNode<T> {
private T value;
private DoublyNode<T> prev;
private DoublyNode<T> next;
/**
* Constructs a new node with a null value and no prev/next.
*/
public DoublyNode() {
value = null;
prev = null;
next = null;
}
/**
* Constructs a new node with a specific value and no prev/next.
* @param value the value for this node
*/
public DoublyNode(T value) {
this.value = value;
prev = null;
next = null;
}
/**
* Constructs a new node with a specific value, prev, and next.
* @param value the value for this node
* @param prev the previous node
* @param next the next node
*/
public DoublyNode(T value, DoublyNode<T> prev, DoublyNode<T> next) {
this.value = value;
this.prev = prev;
this.next = next;
}
/**
* @return the value associated to this node.
*/
public T getValue() {
return value;
}
/**
* Changes the value associated to this node.
* @param value the new value for this node
*/
public void setValue(T value) {
this.value = value;
}
/**
* @return the previous node.
*/
public DoublyNode<T> getPrev() {
return prev;
}
/**
* Changes the previous node.
* @param prev the new previous node
*/
public void setPrev(DoublyNode<T> prev) {
this.prev = prev;
}
/**
* @return the next node.
*/
public DoublyNode<T> getNext() {
return next;
}
/**
* @return true iff getNext() != null.
*/
public boolean hasNext() {
return next != null;
}
/**
* Changes the next node.
* @param next the new next node
*/
public void setNext(DoublyNode<T> next) {
this.next = next;
}
}
// DoublyLinkedList.java
package collections;
/**
* This class represents a list implemented over doubly-linked nodes.
*/
public class DoublyLinkedList<T> {
private DoublyNode<T> head;
private DoublyNode<T> tail;
private int size;
/**
* Constructs a new empty list.
*/
public DoublyLinkedList() {
head = null;
tail = null;
size = 0;
}
/**
* Constructs a new list from another, the elements of the other list will be added to this list.
* @param from the other list from where to construct this
*/
public DoublyLinkedList(DoublyLinkedList<T> from) {
head = null;
tail = null;
size = 0;
if (from == null) {
throw new IllegalArgumentException("the other list cannot be null");
}
DoublyNode<T> current = from.head;
while (current != null) {
add(current.getValue());
current = current.getNext();
}
}
/**
* Adds a value to the end of this list.
* @param value the value to add
*/
public void add(T value) {
DoublyNode<T> newNode = new DoublyNode<>(value);
if (head == null) {
head = newNode;
tail = newNode;
} else {
newNode.setPrev(tail);
tail.setNext(newNode);
tail = newNode;
}
size++;
}
/**
* Adds a value to the end of this list.
* @param value the value to add
*/
public void append(T value) {
add(value);
}
/**
* Adds a value to the beginning of this list, shifting all existing elements one place to the right.
* @param value the value to add
*/
public void prepend(T value) {
DoublyNode<T> newNode = new DoublyNode<>(value);
if (head == null) {
head = newNode;
tail = newNode;
} else {
newNode.setNext(head);
head.setPrev(newNode);
head = newNode;
}
size++;
}
/**
* Adds a value at a specific position shifting all values starting from that position one place to the right.
* @param value the value to add
* @param at the index at which to add.
*/
public void addAt(T value, int at) {
if (at < 0) {
throw new IllegalArgumentException("at is negative or out of bound!");
}
if (at == 0) {
prepend(value);
return;
}
if (at >= size) {
append(value);
return;
}
DoublyNode<T> current = head;
for (int i = 0; i < at; i++) {
current = current.getNext();
}
DoublyNode<T> newNode = new DoublyNode<>(value, current.getPrev(), current);
if (current.getPrev() != null) {
current.getPrev().setNext(newNode);
}
current.setPrev(newNode);
size++;
}
/**
* Returns the element at a given position.
* @param i the index of the element to retrieve
* @return the element at position i.
*/
public T at(int i) {
if (i < 0 || i >= size) {
throw new IllegalArgumentException("i is negative or out of bound!");
}
DoublyNode<T> current = head;
for (int j = 0; j < i; j++) {
current = current.getNext();
}
return current.getValue();
}
/**
* Returns the first element of this list.
* @return the first element of this list.
*/
public T first() {
if (size == 0) {
throw new IllegalStateException("List is empty");
}
return at(0);
}
/**
* Returns the last element of this list.
* @return the last element of this list.
*/
public T last() {
if (size == 0) {
throw new IllegalStateException("List is empty");
}
return at(size - 1);
}
/**
* Removes the value at a specific position shifting all values starting from the next position one place to the left.
* @param at the index of the element to remove.
*/
public void removeAt(int at) {
if (at < 0 || at >= size) {
throw new IllegalArgumentException("at is negative or out of bound!");
}
DoublyNode<T> current = head;
for (int i = 0; i < at; i++) {
current = current.getNext();
}
if (current.getPrev() != null) {
current.getPrev().setNext(current.getNext());
}
if (current.getNext() != null) {
current.getNext().setPrev(current.getPrev());
}
if (current == head) {
head = current.getNext();
}
if (current == tail) {
tail = current.getPrev();
}
size--;
}
/**
* Removes the first value of the list shifting all values from position 1 one place to the left.
*/
public void removeFirst() {
if (size == 0) {
throw new IllegalStateException("List is empty");
}
removeAt(0);
}
/**
* Removes the last value of the list.
*/
public void removeLast() {
if (size == 0) {
throw new IllegalStateException("List is empty");
}
removeAt(size - 1);
}
/**
* Checks whether an element is contained in this list.
* @param value the value to search
* @return true if the value is found, false otherwise
*/
public boolean contains(T value) {
DoublyNode<T> current = head;
while (current != null) {
T currentValue = current.getValue();
if ((currentValue == null && value == null) || (currentValue != null && currentValue.equals(value))) {
return true;
}
current = current.getNext();
}
return false;
}
/**
* @return the size of this list
*/
public int size() {
return size;
}
/**
* Returns a string representation of this list with the format [<elements>],
* where <elements> is a comma separated list of the string representation of each element on this list.
* @return a string representation of this list
*/
@Override
public String toString() {
String result = "[";
DoublyNode<T> current = head;
while (current != null) {
result += (current.getValue() == null ? "null" : current.getValue());
if (current.hasNext()) {
result += ", ";
}
current = current.getNext();
}
result += "]";
return result;
}
}
// ArrayList.java
package collections;
import java.util.Objects;
/**
* This class represents a list implemented over a dynamic array.
*/
public class ArrayList<T> {
private static final float EXPANSION_RATIO_DEFAULT = 0.5f;
private static final int CAPACITY_DEFAULT = 10;
// Object[] array: Used to store the elements of the list generically. Since Java generics are erased at runtime,
// we use an array of Object and cast to T when retrieving elements. This allows storing any type T.
private Object[] array;
private int size;
// expansionRatio: Controls how much the array grows when it needs to expand. A value of 0.5 means the array size
// increases by 50% of its current size each time it expands. This balances between memory usage and frequency of
// reallocations. Using a float allows for fractional growth calculations.
private float expansionRatio;
/**
* Constructs a new empty list.
*/
public ArrayList() {
array = new Object[CAPACITY_DEFAULT];
size = 0;
expansionRatio = EXPANSION_RATIO_DEFAULT;
}
/**
* Constructs a new list from another, the elements of the other list will be added to this list.
* preconditions:
* <ul>
* <li>the other list cannot be {@code null}</li>
* </ul>
* @param from the other list from where to construct this
*/
public ArrayList(ArrayList<T> from) {
if (from == null) {
throw new IllegalArgumentException("the other list cannot be null");
}
array = new Object[Math.max(CAPACITY_DEFAULT, from.size())];
size = 0;
expansionRatio = EXPANSION_RATIO_DEFAULT;
for (int i = 0; i < from.size(); i++) {
add(from.at(i));
}
}
/**
* Adds a value to the end of this list.
* @param value the value to add
*/
public void add(T value) {
add(value, size);
}
/**
* Adds a value to the end of this list.
* @param value the value to add
*/
public void append(T value) {
add(value);
}
/**
* Adds a value to the beginning of this list, shifting all existing elements one place to the right.
* @param value the value to add
*/
public void prepend(T value) {
add(value, 0);
}
/**
* Adds a value at a specific position shifting all values starting from that position one place to the right.
* Calling with an index greater or equal to size() is equivalent to calling add(T).
* @param value the value to add
* @param at the index at which to add.
*/
public void addAt(T value, int at) {
add(value, at);
}
// Private method adapted from reference: adds an element at a specific index, ensuring capacity and shifting elements.
private void add(T elem, int i) {
if (i < 0 || i > size) {
throw new IllegalArgumentException("at is negative or out of bound!");
}
ensureCapacity();
shiftToRight(i, size - 1);
array[i] = elem;
size++;
}
/**
* Returns the element at a given position.
* @param i the index of the element to retrieve
* @return the element at position i.
*/
public T at(int i) {
if (i < 0 || i >= size) {
throw new IllegalArgumentException("i is negative or out of bound!");
}
return elementData(i);
}
/**
* Returns the first element of this list.
* @return the first element of this list.
*/
public T first() {
if (size == 0) {
throw new IllegalStateException("List is empty");
}
return at(0);
}
/**
* Returns the last element of this list.
* @return the last element of this list.
*/
public T last() {
if (size == 0) {
throw new IllegalStateException("List is empty");
}
return at(size - 1);
}
/**
* Removes the value at a specific position shifting all values starting from the next position one place to the left.
* @param at the index of the element to remove.
*/
public void removeAt(int at) {
remove(at);
}
/**
* Removes the first value of the list shifting all values from position 1 one place to the left.
*/
public void removeFirst() {
if (size == 0) {
throw new IllegalStateException("List is empty");
}
remove(0);
}
/**
* Removes the last value of the list.
*/
public void removeLast() {
if (size == 0) {
throw new IllegalStateException("List is empty");
}
remove(size - 1);
}
// Private method adapted from reference: removes an element at a specific index by shifting elements left.
private void remove(int i) {
if (i < 0 || i >= size) {
throw new IllegalArgumentException("at is negative or out of bound!");
}
shiftToLeft(i + 1, size - 1);
size--;
}
/**
* Checks whether an element is contained in this list.
* @param value the value to search
* @return true if the value is found, false otherwise
*/
public boolean contains(T value) {
return searchFirstIndexOf(value) >= 0;
}
/**
* @return the size of this list
*/
public int size() {
return size;
}
/**
* Returns a string representation of this list with the format [<elements>],
* where <elements> is a comma separated list of the string representation of each element on this list.
* @return a string representation of this list
*/
@Override
public String toString() {
String result = "[";
for (int i = 0; i < size; i++) {
result += (array[i] == null ? "null" : array[i]);
if (i < size - 1) {
result += ", ";
}
}
result += "]";
return result;
}
// Helper method to safely cast array element to T.
@SuppressWarnings("unchecked")
private T elementData(int i) {
return (T) array[i];
}
// ensureCapacity: This method checks if the array needs expansion before adding a new element. It throws an exception
// if size somehow exceeds array length (invariant check), and expands the array by the expansion ratio if full.
// Expansion creates a new larger array and copies elements, which is O(n) time but amortized over multiple adds.
// Reason: Prevents index out of bounds by proactively growing the backing array, using a growth factor to minimize
// frequent reallocations while controlling memory overhead.
private void ensureCapacity() {
if (size > array.length) {
throw new IllegalStateException("the size became greater than the capacity of the array");
} else if (size == array.length) {
int newSize = array.length + (int) (array.length * expansionRatio);
Object[] newArray = new Object[newSize];
for (int i = 0; i < size; i++) {
newArray[i] = array[i];
}
array = newArray;
}
}
// shiftToRight: Shifts elements from 'from' to 'to' one position to the right to make space for insertion at 'from'.
// Reason: Efficiently creates a gap in the array for the new element without using extra space, though it's O(n) in worst case for insertions at the beginning.
private void shiftToRight(int from, int to) {
for (int i = to; i >= from; i--) {
array[i + 1] = array[i];
}
}
// shiftToLeft: Shifts elements from 'from' to 'to' one position to the left to fill the gap after removal.
// Reason: Closes the gap left by the removed element, maintaining contiguous storage, O(n) in worst case for removals at the beginning.
private void shiftToLeft(int from, int to) {
for (int i = from; i <= to; i++) {
array[i - 1] = array[i];
}
}
// searchFirstIndexOf: Searches for the first occurrence of the element using Objects.equals for comparison,
// which safely handles null values and calls equals() on non-null objects.
// Reason: Provides a way to find elements respecting object equality (not reference equality), essential for contains() and remove(T).
// Using Objects.equals avoids NullPointerException when comparing with null.
private int searchFirstIndexOf(T elem) {
int indexOf = 0;
boolean found = false;
while (indexOf < size && !found) {
T current = elementData(indexOf);
found = Objects.equals(elem, current);
if (!found) {
indexOf++;
}
}
return found ? indexOf : -1;
}
}
# DoublyNode.py
class DoublyNode:
def __init__(self, value=None, prev=None, next=None):
self.value = value
self.prev = prev
self.next = next
def getValue(self):
return self.value
def setValue(self, value):
self.value = value
def getPrev(self):
return self.prev
def setPrev(self, prev):
self.prev = prev
def getNext(self):
return self.next
def hasNext(self):
return self.next is not None
def setNext(self, next):
self.next = next
# DoublyLinkedList.py
class DoublyLinkedList:
def __init__(self, from_list=None):
self.head = None
self.tail = None
self._size = 0
if from_list is not None:
if from_list is None:
raise ValueError("the other list cannot be null")
current = from_list.head
while current is not None:
self.add(current.getValue())
current = current.getNext()
def add(self, value):
new_node = DoublyNode(value)
if self.head is None:
self.head = new_node
self.tail = new_node
else:
new_node.setPrev(self.tail)
self.tail.setNext(new_node)
self.tail = new_node
self._size += 1
def append(self, value):
self.add(value)
def prepend(self, value):
new_node = DoublyNode(value)
if self.head is None:
self.head = new_node
self.tail = new_node
else:
new_node.setNext(self.head)
self.head.setPrev(new_node)
self.head = new_node
self._size += 1
def addAt(self, value, at):
if at < 0:
raise ValueError("at is negative or out of bound!")
if at == 0:
self.prepend(value)
return
if at >= self._size:
self.append(value)
return
current = self.head
for i in range(at):
current = current.getNext()
new_node = DoublyNode(value, current.getPrev(), current)
if current.getPrev() is not None:
current.getPrev().setNext(new_node)
current.setPrev(new_node)
if at == 0:
self.head = new_node
self._size += 1
def at(self, i):
if i < 0 or i >= self._size:
raise ValueError("i is negative or out of bound!")
current = self.head
for j in range(i):
current = current.getNext()
return current.getValue()
def first(self):
if self._size == 0:
raise ValueError("List is empty")
return self.at(0)
def last(self):
if self._size == 0:
raise ValueError("List is empty")
return self.at(self._size - 1)
def removeAt(self, at):
if at < 0 or at >= self._size:
raise ValueError("at is negative or out of bound!")
if self._size == 0:
raise ValueError("List is empty")
current = self.head
for i in range(at):
current = current.getNext()
if current.getPrev() is not None:
current.getPrev().setNext(current.getNext())
if current.getNext() is not None:
current.getNext().setPrev(current.getPrev())
if current == self.head:
self.head = current.getNext()
if current == self.tail:
self.tail = current.getPrev()
self._size -= 1
def removeFirst(self):
if self._size == 0:
raise ValueError("List is empty")
self.removeAt(0)
def removeLast(self):
if self._size == 0:
raise ValueError("List is empty")
self.removeAt(self._size - 1)
def contains(self, value):
current = self.head
while current is not None:
if current.getValue() == value:
return True
current = current.getNext()
return False
def size(self):
return self._size
def __str__(self):
result = "["
current = self.head
while current is not None:
result += str(current.getValue()) if current.getValue() is not None else "null"
if current.hasNext():
result += ", "
current = current.getNext()
result += "]"
return result
# ArrayList.py
class ArrayList:
def __init__(self, from_list=None):
self._data = []
if from_list is not None:
if from_list is None:
raise ValueError("the other list cannot be null")
current = from_list.head
while current is not None:
self.add(current.getValue())
current = current.getNext()
def add(self, value):
self._data.append(value)
def append(self, value):
self._data.append(value)
def prepend(self, value):
self._data.insert(0, value)
def addAt(self, value, at):
if at < 0:
raise ValueError("at is negative or out of bound!")
if at >= len(self._data):
self.append(value)
else:
self._data.insert(at, value)
def at(self, i):
if i < 0 or i >= len(self._data):
raise ValueError("i is negative or out of bound!")
return self._data[i]
def first(self):
if len(self._data) == 0:
raise ValueError("List is empty")
return self._data[0]
def last(self):
if len(self._data) == 0:
raise ValueError("List is empty")
return self._data[-1]
def removeAt(self, at):
if at < 0 or at >= len(self._data):
raise ValueError("at is negative or out of bound!")
del self._data[at]
def removeFirst(self):
if len(self._data) == 0:
raise ValueError("List is empty")
self.removeAt(0)
def removeLast(self):
if len(self._data) == 0:
raise ValueError("List is empty")
self.removeAt(len(self._data) - 1)
def contains(self, value):
return value in self._data
def size(self):
return len(self._data)
def __str__(self):
return "[" + ", ".join(str(v) if v is not None else "null" for v in self._data) + "]"
// DoublyNode.h
#ifndef DOUBLYNODE_H
#define DOUBLYNODE_H
template <typename T>
class DoublyNode {
private:
T value;
DoublyNode<T>* prev;
DoublyNode<T>* next;
public:
DoublyNode() : value(), prev(nullptr), next(nullptr) {}
DoublyNode(T val) : value(val), prev(nullptr), next(nullptr) {}
DoublyNode(T val, DoublyNode<T>* pr, DoublyNode<T>* nxt) : value(val), prev(pr), next(nxt) {}
T getValue() {
return value;
}
void setValue(T val) {
value = val;
}
DoublyNode<T>* getPrev() {
return prev;
}
void setPrev(DoublyNode<T>* pr) {
prev = pr;
}
DoublyNode<T>* getNext() {
return next;
}
bool hasNext() {
return next != nullptr;
}
void setNext(DoublyNode<T>* nxt) {
next = nxt;
}
};
#endif
// DoublyLinkedList.h
#ifndef DOUBLYLINKEDLIST_H
#define DOUBLYLINKEDLIST_H
#include "DoublyNode.h"
#include <string>
#include <stdexcept>
template <typename T>
class DoublyLinkedList {
private:
DoublyNode<T>* head;
DoublyNode<T>* tail;
int _size;
void clear() {
while (head != nullptr) {
DoublyNode<T>* temp = head;
head = head->getNext();
delete temp;
}
tail = nullptr;
_size = 0;
}
public:
DoublyLinkedList() : head(nullptr), tail(nullptr), _size(0) {}
DoublyLinkedList(DoublyLinkedList<T>* from) : head(nullptr), tail(nullptr), _size(0) {
if (from == nullptr) {
throw std::invalid_argument("the other list cannot be null");
}
DoublyNode<T>* current = from->head;
while (current != nullptr) {
add(current->getValue());
current = current->getNext();
}
}
~DoublyLinkedList() {
clear();
}
// Copy constructor
DoublyLinkedList(const DoublyLinkedList<T>& other) : head(nullptr), tail(nullptr), _size(0) {
DoublyNode<T>* current = other.head;
while (current != nullptr) {
add(current->getValue());
current = current->getNext();
}
}
// Assignment operator
DoublyLinkedList<T>& operator=(const DoublyLinkedList<T>& other) {
if (this != &other) {
clear();
DoublyNode<T>* current = other.head;
while (current != nullptr) {
add(current->getValue());
current = current->getNext();
}
}
return *this;
}
void add(T value) {
DoublyNode<T>* newNode = new DoublyNode<T>(value);
if (head == nullptr) {
head = newNode;
tail = newNode;
} else {
newNode->setPrev(tail);
tail->setNext(newNode);
tail = newNode;
}
_size++;
}
void append(T value) {
add(value);
}
void prepend(T value) {
DoublyNode<T>* newNode = new DoublyNode<T>(value);
if (head == nullptr) {
head = newNode;
tail = newNode;
} else {
newNode->setNext(head);
head->setPrev(newNode);
head = newNode;
}
_size++;
}
void addAt(T value, int at) {
if (at < 0) {
throw std::invalid_argument("at is negative or out of bound!");
}
if (at == 0) {
prepend(value);
return;
}
if (at >= _size) {
append(value);
return;
}
DoublyNode<T>* current = head;
for (int i = 0; i < at; ++i) {
current = current->getNext();
}
DoublyNode<T>* newNode = new DoublyNode<T>(value, current->getPrev(), current);
if (current->getPrev() != nullptr) {
current->getPrev()->setNext(newNode);
}
current->setPrev(newNode);
if (at == 0) {
head = newNode;
}
_size++;
}
T at(int i) {
if (i < 0 || i >= _size) {
throw std::invalid_argument("i is negative or out of bound!");
}
DoublyNode<T>* current = head;
for (int j = 0; j < i; ++j) {
current = current->getNext();
}
return current->getValue();
}
T first() {
if (_size == 0) {
throw std::runtime_error("List is empty");
}
return at(0);
}
T last() {
if (_size == 0) {
throw std::runtime_error("List is empty");
}
return at(_size - 1);
}
void removeAt(int at) {
if (at < 0 || at >= _size) {
throw std::invalid_argument("at is negative or out of bound!");
}
if (_size == 0) {
throw std::runtime_error("List is empty");
}
DoublyNode<T>* current = head;
for (int i = 0; i < at; ++i) {
current = current->getNext();
}
if (current->getPrev() != nullptr) {
current->getPrev()->setNext(current->getNext());
}
if (current->getNext() != nullptr) {
current->getNext()->setPrev(current->getPrev());
}
if (current == head) {
head = current->getNext();
}
if (current == tail) {
tail = current->getPrev();
}
delete current;
_size--;
}
void removeFirst() {
if (_size == 0) {
throw std::runtime_error("List is empty");
}
removeAt(0);
}
void removeLast() {
if (_size == 0) {
throw std::runtime_error("List is empty");
}
removeAt(_size - 1);
}
bool contains(T value) {
DoublyNode<T>* current = head;
while (current != nullptr) {
if (current->getValue() == value) {
return true;
}
current = current->getNext();
}
return false;
}
int size() {
return _size;
}
std::string toString() {
std::string result = "[";
DoublyNode<T>* current = head;
while (current != nullptr) {
result += std::to_string(current->getValue());
if (current->hasNext()) {
result += ", ";
}
current = current->getNext();
}
result += "]";
return result;
}
};
#endif
// ArrayList.h
#ifndef ARRAYLIST_H
#define ARRAYLIST_H
#include <stdexcept>
#include <string>
#include <algorithm>
template <typename T>
class ArrayList {
private:
T* data;
int capacity;
int _size;
void resize() {
if (capacity == 0) {
capacity = 1;
} else {
capacity *= 2;
}
T* newData = new T[capacity];
std::copy(data, data + _size, newData);
delete[] data;
data = newData;
}
public:
ArrayList() : data(nullptr), capacity(0), _size(0) {}
ArrayList(ArrayList<T>* from) : data(nullptr), capacity(0), _size(0) {
if (from == nullptr) {
throw std::invalid_argument("the other list cannot be null");
}
for (int i = 0; i < from->_size; ++i) {
add(from->at(i));
}
}
~ArrayList() {
delete[] data;
}
// Copy constructor
ArrayList(const ArrayList<T>& other) : data(nullptr), capacity(0), _size(0) {
capacity = other._size;
data = new T[capacity];
_size = other._size;
std::copy(other.data, other.data + _size, data);
}
// Assignment operator
ArrayList<T>& operator=(const ArrayList<T>& other) {
if (this != &other) {
delete[] data;
capacity = other._size;
data = new T[capacity];
_size = other._size;
std::copy(other.data, other.data + _size, data);
}
return *this;
}
void add(T value) {
if (_size == capacity) {
resize();
}
data[_size++] = value;
}
void append(T value) {
add(value);
}
void prepend(T value) {
insertAt(value, 0);
}
void addAt(T value, int at) {
if (at < 0) {
throw std::invalid_argument("at is negative or out of bound!");
}
if (at > _size) {
at = _size;
}
insertAt(value, at);
}
void insertAt(T value, int at) {
if (_size == capacity) {
resize();
}
for (int i = _size; i > at; --i) {
data[i] = data[i - 1];
}
data[at] = value;
_size++;
}
T at(int i) {
if (i < 0 || i >= _size) {
throw std::invalid_argument("i is negative or out of bound!");
}
return data[i];
}
T first() {
if (_size == 0) {
throw std::runtime_error("List is empty");
}
return data[0];
}
T last() {
if (_size == 0) {
throw std::runtime_error("List is empty");
}
return data[_size - 1];
}
void removeAt(int at) {
if (at < 0 || at >= _size) {
throw std::invalid_argument("at is negative or out of bound!");
}
for (int i = at; i < _size - 1; ++i) {
data[i] = data[i + 1];
}
_size--;
}
void removeFirst() {
if (_size == 0) {
throw std::runtime_error("List is empty");
}
removeAt(0);
}
void removeLast() {
if (_size == 0) {
throw std::runtime_error("List is empty");
}
removeAt(_size - 1);
}
bool contains(T value) {
for (int i = 0; i < _size; ++i) {
if (data[i] == value) {
return true;
}
}
return false;
}
int size() {
return _size;
}
std::string toString() {
std::string result = "[";
for (int i = 0; i < _size; ++i) {
result += std::to_string(data[i]);
if (i < _size - 1) {
result += ", ";
}
}
result += "]";
return result;
}
};
#endif