链表
| Operation |
Time Complexity |
Space Complexity |
Notes |
| Constructor |
O(1) |
O(1) |
Initializes empty list |
| get(index) |
O(n) |
O(1) |
Traverses to index-th node |
| addAtHead(val) |
O(1) |
O(1) |
Adds node at start |
| addAtTail(val) |
O(n) |
O(1) |
Traverses to end |
| addAtIndex(index, val) |
O(n) |
O(1) |
Traverses to index or end |
| deleteAtIndex(index) |
O(n) |
O(1) |
Traverses to index |
class MyLinkedList {
private:
struct Node {
int val;
Node* next;
Node(int x) : val(x), next(NULL) {}
};
Node* head;
int size;
public:
MyLinkedList() {
head = NULL;
size = 0;
}
int get(int index) {
if (index < 0 || index >= size) return -1;
Node* current = head;
for (int i = 0; i < index; i++) {
current = current->next;
}
return current->val;
}
void addAtHead(int val) {
Node* newNode = new Node(val);
newNode->next = head;
head = newNode;
size++;
}
void addAtTail(int val) {
Node* newNode = new Node(val);
if (head == NULL) {
head = newNode;
} else {
Node* current = head;
while (current->next != NULL) {
current = current->next;
}
current->next = newNode;
}
size++;
}
void addAtIndex(int index, int val) {
if (index < 0 || index > size) return;
if (index == 0) {
addAtHead(val);
return;
}
Node* current = head;
for (int i = 0; i < index - 1; i++) {
current = current->next;
}
Node* newNode = new Node(val);
newNode->next = current->next;
current->next = newNode;
size++;
}
void deleteAtIndex(int index) {
if (index < 0 || index >= size) return;
if (index == 0) {
Node* temp = head;
head = head->next;
delete temp;
size--;
return;
}
Node* current = head;
for (int i = 0; i < index - 1; i++) {
current = current->next;
}
Node* temp = current->next;
current->next = temp->next;
delete temp;
size--;
}
};
链表