It is a abstract data type that represents a sequence of nodes. In other words, it can be implemented in many ways. So, here is my suggestion, try to implement it according to the situation rather than only one way.
Singly Linked List
This structure is the most common one. It is a linear data structure where each element is a separate object. Each element is called a node and every node has two parts, data and pointer to the next node. The first node is called head and the last node is called tail. The tail node points to null.
Design a Linked List
Design a Linked List with head and size attributes
class Node:
def __init__(self, val, next=None):
self.val = val
self.next = next
class LinkedList:
def __init__(self):
self.head = None
self.size = 0
def get(self, index: int) -> int:
if index<0 or index>=self.size:
return -1
curr = self.head
for _ in range(index):
curr=curr.next
if curr is None:
return -1
return curr.val
def addAtHead(self, val: int) -> None:
self.head=Node(val, self.head)
self.size += 1
def addAtTail(self, val: int) -> None:
if self.head is None:
self.head = Node(val)
else:
curr=self.head
while curr.next:
curr=curr.next
curr.next=Node(val)
self.size += 1
def addAtIndex(self, index: int, val: int) -> None:
if index<0 or index>self.size:
return
if index==0:
self.addAtHead(val)
else:
curr=self.head
for _ in range(index-1):
curr=curr.next
curr.next=Node(val, curr.next)
self.size += 1
def deleteAtIndex(self, index: int) -> None:
if index<0 or index>=self.size:
return
if index==0:
self.head=self.head.next
else:
curr=self.head
for _ in range(index-1):
curr=curr.next
curr.next=curr.next.next
self.size -= 1
The Singly Linked List in Rust
Box: A smart pointer type for heap allocation. Option is a type that represents an optional value: every Option is either Some and contains a value, or None, and does not.
struct Node {
val: i32,
next: Option<Box<Node>>,
}
impl Node {
fn new(val: i32) -> Self {
Node {val, next: None}
}
}
struct MyLinkedList {
head: Option<Box<Node>>,
size: i32,
}
impl MyLinkedList {
fn new() -> Self{
MyLinkedList {head: None, size: 0}
}
fn get(&self, index: i32) -> i32 {
if index<0 || index>=self.size{
return -1;
}
let mut curr = &self.head;
let mut i =0;
while let Some(node) = curr{
if i ==index{
return node.val;
}
i+=1;
curr = &node.next;
}
-1
}
fn add_at_head(&mut self, val: i32){
let mut node =Box::new(Node::new(val));
node.next = self.head.take();
self.head=Some(node);
self.size+=1;
}
fn add_at_tail(&mut self, val: i32){
let node=Box::new(Node::new(val));
let mut curr = &mut self.head;
while let Some(node)=curr{
curr=&mut node.next;
}
*curr=Some(node);
self.size+=1;
}
fn add_at_index(&mut self, inex: i32, val:i32){
if index<0 || index>self.size{
return;
}
if index==0{
self.ad_at_head(val);
return;
}
let mut curr = &mut self.head;
let mut i = 0;
while let Some(node) =curr{
if i==index-1{
let mut new_node = Box::new(Node::new(val));
new_node.next=node.next.take();
node.next=Some(new_node);
self.size+=1;
}
i+=1;
curr=&mut node.next
}
}
fn delete_at_index(&mut self, index: i32){
if index<0 || index>=self.size{
return;
}
if index==0{
self.head=self.head.take().unwrap().next.take();
self.size-=1;
return;
}
let mut curr = &mut self.head;
let mut i = 0;
while let Some(node)=curr{
if i==index-1{
node.next=node.next.take().unwrap().next;
self.size-=1;
return;
}
i+=1;
curr=&mut node.next;
}
}
}
Design a Linked List with head, tail and size attributes
class Node:
def __init__(self, val, next=None):
self.val = val
self.next = next
class LinkedList:
def __init__(self):
self.head = None
self.tail = None
self.size = 0
def get(self, index: int) -> int:
if index<0 or index>=self.size:
return -1
curr = self.head
for _ in range(index):
curr=curr.next
if curr is None:
return -1
return curr.val
def addAtHead(self, val: int) -> None:
self.head = Node(val, self.head)
if self.tail is None:
self.tail = self.head
self.size += 1
def addAtTail(self, val: int) -> None:
if self.tail is None:
self.head = self.tail = Node(val)
else:
self.tail.next = Node(val)
self.tail = self.tail.next
self.size += 1
def addAtIndex(self, index: int, val: int) -> None:
if index<0 or index>self.size:
return
if index==0:
self.addAtHead(val)
elif index==self.size:
self.addAtTail(val)
else:
curr = self.head
for _ in range(index-1):
curr = curr.next
curr.next = Node(val, curr.next)
self.size += 1
def deleteAtIndex(self, index: int) -> None:
if index<0 or index>=self.size:
return
curr = self.head
if index==0:
self.head = self.head.next
if self.head is None:
self.tail = None
else:
for _ in range(index-1):
curr = curr.next
curr.next = curr.next.next
if index==self.size-1:
self.tail = curr
self.size -= 1
What is the difference between the two implementations?
The first implementation is more efficient than the second one. The second implementation is more readable than the first one.
The first implementation is more efficient because it does not need to check if the tail is None or not. The second implementation is more readable because it does not need to check if the index is 0 or not.
Doubly Linked List
This structure is similar to the singly linked list. The only difference is that each node has two pointers, one points to the next node and the other points to the previous node. The first node is called head and the last node is called tail. The head node points to null and the tail node points to null.
class Node:
def __init__(self, val, next=None, prev=None):
self.val = val
self.next = next
self.prev = prev
class LinkedList:
def __init__(self):
self.head = None
self.tail = None
self.size = 0
def get(self, index: int) -> int:
if index<0 or index>=self.size:
return -1
curr = self.head
for _ in range(index):
curr=curr.next
if curr is None:
return -1
return curr.val
def addAtHead(self, val: int) -> None:
self.head = Node(val, self.head)
if self.tail is None:
self.tail = self.head
else:
self.head.next.prev = self.head
self.size += 1
def addAtTail(self, val: int) -> None:
if self.tail is None:
self.head = self.tail = Node(val)
else:
self.tail.next = Node(val, None, self.tail)
self.tail = self.tail.next
self.size += 1
def addAtIndex(self, index: int, val: int) -> None:
if index<0 or index>self.size:
return
if index==0:
self.addAtHead(val)
elif index==self.size:
self.addAtTail(val)
else:
curr = self.head
for _ in range(index-1):
curr = curr.next
curr.next = Node(val, curr.next, curr)
curr.next.next.prev = curr.next
self.size += 1
def deleteAtIndex(self, index: int) -> None:
if index<0 or index>=self.size:
return
curr = self.head
if index==0:
self.head = self.head.next
if self.head is None:
self.tail = None
else:
self.head.prev = None
else:
for _ in range(index-1):
curr = curr.next
curr.next = curr.next.next
if index==self.size-1:
self.tail = curr
else:
curr.next.prev = curr
self.size -= 1
Why we need Doubly Linked List? Is it more efficient than Singly Linked List?
Doubly Linked List is useful when we need to traverse the linked list in both forward and backward directions. It provides a prev pointer in addition to the next pointer, which allows us to traverse the list in reverse order. However, it requires more memory than a Singly Linked List due to the extra prev pointer. In terms of time complexity, both types of linked lists have the same time complexity for most operations, such as insertion and deletion.
What are the techniques to solve the linked list problems?
For exmaple, how to find the linked list middle node, or it has a cycle or not.
Here is an example of checking if the linked list has a cycle or not.
# Definition for singly-linked list.
class Node:
def __init__(self, x):
self.val = x
self.next = None
class Solution:
def hasCycle(self, head: Optional[ListNode]):
slow = fast = head
while fast and fast.next:
slow = slow.next
fast = fast.next.next
if slow == fast:
return True
return False