Brossh Interview Question
Developer Program EngineersCountry: Isreal
Interview Type: Written Test
I implemented a simple double linked list in Python:
class Node:
def __init__(self, value=None, left=None, right=None):
self.value = value
self.left = left
self.right = right
def append(self, value):
if self.right is not None:
self.right.append(value)
else:
self.right = Node(value, self)
def remove(self, value):
if self.value == value:
if self.left is not None:
self.left.right = self.right
else:
self.value = self.right.value
self.right = self.right.right
self.right.left = self
if self.right is not None:
self.right.remove(value)
def as_list(self):
ret_list = list()
Node._as_list(self, ret_list)
return ret_list
@staticmethod
def _as_list(node, ret_list):
ret_list.append(node.value)
if node.right is not None:
Node._as_list(node.right, ret_list)
class DLinkedList:
def __init__(self, numbers_list=None):
self.root = DLinkedList._generate_nodes(numbers_list if numbers_list is not None else [])
@staticmethod
def _generate_nodes(numbers_list):
if len(numbers_list) == 0:
return None
root = None
for number in numbers_list:
if root is None:
root = Node(number)
else:
root.append(number)
return root
def as_list(self):
if self.root is None:
return []
return self.root.as_list()
def remove(self, element):
if self.root is None:
return
return self.root.remove(element)
dlinked_list = DLinkedList([1, 2, 43, 1, 56, 12, 5, 1, -2, 4333, 3])
print(dlinked_list.as_list())
dlinked_list.remove(43)
print(dlinked_list.as_list())
dlinked_list.remove(1)
print(dlinked_list.as_list())
#include <iostream>
template <typename T>
class Node {
public:
T data;
Node* prev;
Node* next;
Node(T val) : data(val), prev(nullptr), next(nullptr) {}
};
template <typename T>
class DoublyLinkedList {
private:
Node<T>* head;
Node<T>* tail;
int size;
public:
DoublyLinkedList() : head(nullptr), tail(nullptr), size(0) {}
~DoublyLinkedList() {
while (head != nullptr) {
Node<T>* temp = head;
head = head->next;
delete temp;
}
}
void insertFront(T val) {
Node<T>* newNode = new Node<T>(val);
if (head == nullptr) {
head = tail = newNode;
} else {
newNode->next = head;
head->prev = newNode;
head = newNode;
}
++size;
}
void insertBack(T val) {
Node<T>* newNode = new Node<T>(val);
if (tail == nullptr) {
head = tail = newNode;
} else {
newNode->prev = tail;
tail->next = newNode;
tail = newNode;
}
++size;
}
void removeFront() {
if (head == nullptr) {
std::cout << "List is empty. Cannot remove from an empty list.\n";
return;
}
Node<T>* temp = head;
head = head->next;
if (head != nullptr) {
head->prev = nullptr;
} else {
tail = nullptr; // If head is null, the list is empty, so set tail to null as well.
}
delete temp;
size--;
}
void removeBack() {
if (tail == nullptr) {
std::cout << "List is empty. Cannot remove from an empty list.\n";
return;
}
Node<T>* temp = tail;
tail = tail->prev;
if (tail != nullptr) {
tail->next = nullptr;
} else {
head = nullptr; // If tail is null, the list is empty, so set head to null as well.
}
delete temp;
--size;
}
void display() {
Node<T>* current = head;
while (current != nullptr) {
std::cout << current->data << " ";
current = current->next;
}
std::cout << std::endl;
}
int getSize() const {
return size;
}
};
int main() {
DoublyLinkedList<int> dll;
dll.insertFront(1);
dll.insertFront(2);
dll.insertBack(3);
dll.insertBack(4);
std::cout << "Doubly Linked List: ";
dll.display(); // Output: 2 1 3 4
dll.removeFront();
dll.removeBack();
std::cout << "Doubly Linked List after removal: ";
dll.display(); // Output: 1 3
std::cout << "Size of Doubly Linked List: " << dll.getSize() << std::endl; // Output: 2
return 0;
}
Doubly Linked List: 2 1 3 4
Doubly Linked List after removal: 1 3
Size of Doubly Linked List: 2
Output:
Search google for "doubly linked list in c", doubly linked list is quite commonly asked question.
- PeyarTheriyaa December 10, 2018the one from tutorials point is good enough and quite exhaustive.
ignore functions you don't need and comments