Skip to content

Instantly share code, notes, and snippets.

@harish-r
Created September 6, 2014 07:18
Show Gist options
  • Save harish-r/873ce92a91bb7b685b81 to your computer and use it in GitHub Desktop.
Save harish-r/873ce92a91bb7b685b81 to your computer and use it in GitHub Desktop.
Linked List Implementation in C++
// Linked List CPP
#include<iostream>
using namespace std;
class Node
{
public:
int data;
Node *next;
};
class List
{
Node *head;
Node *tail;
Node *temp;
bool isEmpty()
{
return head == NULL;
}
public:
List()
{
head = NULL;
tail = NULL;
}
void insert(int x)
{
temp = new Node;
temp->data = x;
if(isEmpty())
{
temp->next = NULL;
tail = temp;
}
else
temp->next = head;
head = temp;
}
void insertAtEnd(int x)
{
temp = new Node;
temp->data = x;
temp->next = NULL;
if(isEmpty())
{
head = temp;
tail = temp;
}
else
{
tail->next = temp;
tail = temp;
}
}
void remove(int x)
{
temp = head;
Node *prev;
while(temp->next != NULL && temp->data != x)
{
prev = temp;
temp = temp->next;
}
if(temp->data == x)
{
prev->next = temp->next;
delete temp;
}
else if(temp->next == NULL)
{
cout << "Error: Number Not found..." << endl;
}
}
void find(int x)
{
int i;
for(i=1, temp = head;temp->next != NULL && temp->data != x;temp = temp->next, i++);
if(temp->data == x)
{
cout << "Found at position:" << i << endl;
}
else if(temp->next == NULL)
{
cout << "Error: Number Not found..." << endl;
}
}
void display()
{
if(!isEmpty())
{
for(temp = head; temp != NULL; temp=temp->next)
cout << temp->data << " ";
cout << endl;
}
else
{
cout << "List is Empty!" << endl;
}
}
};
int main()
{
List l;
l.display();
l.insert(15);
l.display();
l.insert(25);
l.display();
l.insert(35);
l.display();
l.insert(45);
l.display();
l.find(15);
l.remove(25);
l.display();
l.insertAtEnd(55);
l.insertAtEnd(65);
l.display();
}
@randuhmm
Copy link

I noticed a few issues with the remove method in this implementation:

  1. Removing the first element in the list does not properly set the head pointer to the next element.
  2. Removing the last element in the list does not properly set the tail pointer to the second to last element.
  3. The pointers head/tail are not set to NULL if we remove all of the elements.

Basically there are some edge cases unaccounted for as well as cleanup due to removing first/last elements. Otherwise, thanks for the gist!

@benapie
Copy link

benapie commented Jan 6, 2019

It's better to set your pointers to nullptr rather than NULL.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment