DEV Community

Mohamed Khaled Yousef

Posted on • Updated on

linked list is a data structure that having a list of elements and each element has a reference pointing to the next element in the list.

First thing we have to know about linked list is we have a head pointer that points to a node that then has some date and points to another node and so on till a node that dose not point to any farther.
And node contains 2 elements ,the value or the key (number like 7) and a pointer that points to the next node that contain (another number like 10 for example)

7 →10

There are operations that can be done on linked list called List API

1-On the front of the list:
2-Key TopFront(): return the front element
3-PopFront(): remove the front element

2-On the end of the list
1-PushBack(key): add to back … also known a Append
2-Key TopBack(): return the back element
3-PopBack(): remove the back element
There is difference between the front and back operation in run time

3-We can also do:
1-Boolean Find(Key): is key in a list?
2-Erase(Key): remove key from list
3-Boolean Empty(): empty list?

Example:

we have an empty list ,do this following operations:
PushBack(a);
PushFront(b);
PushBack(d);
PushFront(c);
PopBack();

Solution:
PushBack(a); a
PushFront(b); b a
PushBack(d); b a d
PushFront(c); c b a d
PopBack(); c b a
so,the final result is => c b a

The run time for some operations
PushFront(key): add to front in O(1)
Key TopFront(): return the front element in O(1)
PopFront(): remove the front element O(1)
PushBack(key): add to back in O(n) without no tail
PushBack(key): add to back in O(1) with tail
Key TopBack(): return the back element in O(n) without tail
Key TopBack(): return the back element in O(1) with tail
PopBack(): remove the back element in O(n)

NOTEs::

WHEN we want to push at the back?
1-If We don’t have a tail pointer, So this going to be expensive operation. WHY? because we start at the head and walk our way down the list untill we get to the end and in the end we add a node so its going to be O(n). Similarly if we want to TopBack or PopBack
2-If we had a tail pointer, some of this will become simpler. WHY? because we are going to have both a head pointer that points to the head element ,and tail pointer that points to the tail element. So the first element and the last element became cheap operations.
For example: when we have tail pointer and we want to insert element
-We first allocate a node and put in our new key
-Then update the next pointer of the current tail to point to this new tail
-Then update the tail pointer itself
-And the run time will be O(1)

WHEN we have tail pointer and we want to delete or PopBack element:
-Here we don’t have pointer that points from the last element to the previous last (the element before)
-We only have a pointer from the previous to the last element and that pointer does not help us going back
-So what we have got to do is:
-We start from the head and walk our way down until we find the previous last element or node that points to the current tail (last element)
-Then update our tail pointer to point to that (previous last element)
-Then update the tail pointer to be null, this means tail pointer points to the previous last element which it became the tail element
-Then we can remove the last element
-And the final run time will be O(n) Because we have got to walk all the way down

PushFront

``````node <- new node
if tail = nil: //an empty list
``````

PopFront

``````if head = nil:
ERROR: empty list
tail <- nil
``````

PushBack

``````node <- new node
node.key <- key
node.next = nil
if tail = nil;
else:
tail.next <- node,
tail <- node
``````

PopBack

``````if head = nil :
ERROR: empty list
else
while p.next.next != nil:
p <- p.next
p.next <- nil;
tail <- p
``````

``````node <- new node
node.key <- key
node.next = node.next
node.next = node
if tail = node: //one element in list and this is the same node that we want to add key after that
tail <- node
``````

Adding before have the same problem we had with Pop back that we don’t have a link back to the previous element so AddBefore would be an O(n)

Here you can find all main operations that we can do on single linked list:

``````#include<iostream>
using namespace std;

//built node .... node = (data and pointer)
struct node
{
int data;   //data item
node* next; //pointer to next node
};
{
private:
public:
{
}
void deleteElement(int d);
void display();
};

//Push front code
{
node* newNode=new node;
newNode->data=d;
}

//Push back code
{
node* newNode=new node;
node* temp=new node;
newNode->data=x;
if(temp==NULL)
{
newNode->next=NULL;
return;
}

while(temp->next!=NULL)
{
temp=temp->next;
}

newNode->next=NULL;
temp->next=newNode;
}

//if d=5,key=2
{
node* search=new node;
while(search!=NULL)
{
if(search->data==d)
{
node* newNode=new node;
newNode->data=key;
newNode->next=search->next;
search->next=newNode;
return;
}
search=search->next;
}

if(search==NULL)
}

{
node* del;
if(del==NULL)
{
return;
}
if(del->data==d)
{
return;
}
if(del->next==NULL)
{
cout<<"Is not here, So not deleted."<<endl;
return;
}
//if here more one nodes...one node points to another node ... bigger than 2 nodes .. at least 2 nodes
while(del->next!=NULL)
{
if(del->next->data==d)
{
del->next=del->next->next;
return;
}

del=del->next;
}

cout<<"Is not here, So not deleted."<<endl;
}

{
int n=0;             //counter for number of node
if (current==NULL)
while(current!=NULL) //until current reach to null(last element)
{
cout<<"The node data number "<<++n<<" is "<<current->data<<endl;
current=current->next;
}
cout<<endl;
}

int main()
{
li.display();       //empty list
li.display();
//64
//49
//36
//25
cout<<endl;

li.display();
cout<<endl;
cout<<"linked list after adding 10 after node that has data = 49"<<endl;
li.display();
li.deleteElement(49);
li.display();