Skip to content

Instantly share code, notes, and snippets.

@m-primo
Created April 25, 2020 14:05
Show Gist options
  • Save m-primo/6f779348c784f517f5f0af000f109721 to your computer and use it in GitHub Desktop.
Save m-primo/6f779348c784f517f5f0af000f109721 to your computer and use it in GitHub Desktop.
Simple Single Linked List Implementation in C++
#include <iostream>
using namespace std;
#define null 0
class Node {
public:
int data;
Node *next;
Node(int data) {
this->data = data;
next = NULL;
}
};
class LinkedList {
private:
Node *head;
Node *tail;
int size;
public:
LinkedList() {
head = NULL;
tail = NULL;
size = 0;
}
void append(int data) {
Node *node = new Node(data);
if(head == NULL) {
head = node;
tail = node;
} else {
tail->next = node;
tail = node;
}
size++;
}
void prepend(int data) {
Node *node = new Node(data);
if(head == NULL) {
head = node;
tail = node;
} else {
node->next = head;
head = node;
}
size++;
}
void insertAt(int data, int pos) {
if(pos > size+1 || pos < 1) return;
else if(pos == 1) prepend(data);
else if(pos == size+1) append(data);
else if(head != NULL) {
Node *node = new Node(data);
Node *prev;
Node *current = head;
for(int i = 1; i < pos; i++) {
prev = current;
current = current->next;
}
prev->next = node;
node->next = current;
size++;
}
}
void removeHead() {
if(head != NULL) {
Node *current = head;
head = head->next;
delete(current);
size--;
}
}
void removeTail() {
if(head->next == NULL) removeHead();
else if(head != NULL) {
Node *current = head;
Node *prev;
while(current->next != NULL) {
prev = current;
current = current->next;
}
tail = prev;
prev->next = NULL;
delete(current);
size--;
}
}
void removeAt(int pos) {
if(pos > size || pos < 1) return;
else if(pos == 1) removeHead();
else if(pos == size) removeTail();
else if(head != NULL) {
Node *prev;
Node *current = head;
for(int i = 1; i < pos; i++) {
prev = current;
current = current->next;
}
prev->next = current->next;
delete(current);
size--;
}
}
void remove(int data) {
if(head != NULL) {
Node *current = head;
if(current->data == data) {
head = head->next;
delete(current);
} else {
while(current != NULL) {
if(current->next->data == data) {
current->next = current->next->next;
break;
} else {
current = current->next;
}
}
}
}
}
void print() {
Node *current = head;
while(current != NULL) {
cout << current->data << endl;
current = current->next;
}
cout << endl;
}
void test() {
prepend(3);
prepend(1);
prepend(5);
print();
append(8);
append(7);
print();
insertAt(2, 9);
insertAt(4, 11);
print();
removeHead();
print();
removeAt(3);
print();
removeTail();
print();
}
~LinkedList() {
Node *current;
while(head != NULL) {
current = head->next;
delete(head);
head = current;
}
head = NULL;
tail = NULL;
}
};
int main() {
LinkedList list;
list.test();
return 0;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment