Data Structures & Algorithms – Arrays and linked lists
Arrays and linked lists are two commonly used data structures for storing and manipulating collections of data.
- Arrays: An array is a data structure that stores a fixed-size collection of elements of the same data type. Elements are stored in contiguous memory locations, and each element can be accessed by its index. For example, an array of integers would store a fixed-size collection of integers, and each integer can be accessed by its index in the array. The time complexity of accessing an element in an array is O(1) which makes it efficient for random access.
Here is an example of how to implement an array in Python:
class Array:
def __init__(self, size):
self.size = size
self.array = [None] * size
def __getitem__(self, index):
return self.array[index]
def __setitem__(self, index, value):
self.array[index] = value
def __len__(self):
return self.size
def __iter__(self):
return iter(self.array)
And here is an example of how to implement an array in JavaScript:
class Array {
constructor(size) {
this.size = size;
this.array = new Array(size);
}
get(index) {
return this.array[index];
}
set(index, value) {
this.array[index] = value;
}
length() {
return this.size;
}
}
- Linked Lists: A linked list is a data structure that stores a collection of elements called nodes, where each node contains a reference to the next node in the list. The first node is called the head, and the last node is called the tail. Linked lists do not store elements in contiguous memory locations and therefore, do not provide constant time access like arrays. However, linked lists have the advantage of dynamic memory allocation, which means that the size of the list can be changed at runtime.
Here is an example of how to implement a singly linked list in Python:
class Node:
def __init__(self, data):
self.data = data
self.next = None
class LinkedList:
def __init__(self):
self.head = None
def insert_head(self, data):
new_node = Node(data)
new_node.next = self.head
self.head = new_node
def insert_tail(self, data):
new_node = Node(data)
if self.head is None:
self.head = new_node
return
current = self.head
while current.next is not None:
current = current.next
current.next = new_node
def delete(self, data):
if self.head is None:
return
if self.head.data == data:
self.head = self.head.next
return
current = self.head
while current.next is not None:
if current.next.data == data:
current.next = current.next.next
return
current = current.next
And here is an example of how to implement a singly linked list in JavaScript:
class Node {
constructor(data) {
this.data = data;
this.next = null;
}
}
class LinkedList {
constructor() {
this.head = null;
}
insertHead(data) {
let newNode = new Node(data);
newNode.next = this.head;
this.head = newNode;
}
insertTail(data) {
let newNode = new Node(data);
if (!this.head) {
this.head = newNode;
return;
}
let current = this.head;
while (current.next) {
current = current.next;
}
current.next = newNode;
}
delete(data) {
if (!this.head) {
return;
}
if (this.head.data === data) {
this.head = this.head.next;
return;
}
let current = this.head;
while (current.next) {
if (current.next.data === data) {
current.next = current.next.next;
return;
}
current = current.next;
}
}
}
And here is an example of how to implement a singly linked list in Java:
class Node {
int data;
Node next;
public Node(int data) {
this.data = data;
this.next = null;
}
}
class LinkedList {
Node head;
public void insertHead(int data) {
Node newNode = new Node(data);
newNode.next = head;
head = newNode;
}
public void insertTail(int data) {
Node newNode = new Node(data);
if (head == null) {
head = newNode;
return;
}
Node current = head;
while (current.next != null) {
current = current.next;
}
current.next = newNode;
}
public void delete(int data) {
if (head == null) {
return;
}
if (head.data == data) {
head = head.next;
return;
}
Node current = head;
while (current.next != null) {
if (current.next.data == data) {
current.next = current.next.next;
return;
}
current = current.next;
}
}
}
And here is an example of how to implement a singly linked list in Rust:
struct Node {
data: i32,
next: Option<Box<Node>>
}
struct LinkedList {
head: Option<Box<Node>>
}
impl LinkedList {
fn new() -> Self {
LinkedList { head: None }
}
fn insert_head(&mut self, data: i32) {
let new_node = Box::new(Node {
data: data,
next: self.head.take()
});
self.head = Some(new_node);
}
fn insert_tail(&mut self, data: i32) {
let mut current = &mut self.head;
while let Some(ref mut node) = current {
current = &mut node.next;
}
*current = Some(Box::new(Node { data, next: None }));
}
fn delete(&mut self, data: i32) {
self.head = match self.head.take() {
None => None,
Some(mut first) => {
if first.data == data {
first.next
} else {
let mut current = &mut first;
while let Some(ref mut node) = current.next {
if node.data == data {
current.next = node.next.take();
break;
}
current = node;
}
Some(first)
}
}
};
}
}
In conclusion, Arrays and linked lists are two commonly used data structures for storing and manipulating collections of data. Arrays provide constant time access while linked lists allow dynamic memory allocation. Both data structures have their own use cases and trade-offs, and it is important to understand the requirements of your application before choosing a data structure. The examples provided are basic implementations of the data structures and may not be suitable for production use without additional error handling and optimization.