Introduction
Nothing to say more than hello 👋,
In Case your wondering who is this man in the banner it's the Khwarizmi the inventor of algorithms concept.
Make sure to follow because I will start more advanced series in future.
Linked List
Single Linked List
struct node
{
char data;
struct node *next;
}
self reference structures we talk about them before.
first element is called head.
arrays are dynamic access , while linked lists are sequential accessible , it mean you need to visit all the previous element in order to reach the element you need , it mean O(n) while arrays are O(1)
searching in both will take O(n) .
struct node *p;
p = head->next->next; // 30
p->next->next->next=p; // 50 will link to 30 , so 60 is lost
head->next=p->next; // 10 will link to 40
printf("%c" , head->next->next->next->next->data); // d
This linked list is same for all the followings. We are assuming that our linked list have more than 1 node , if it is 1 node we should put conditions to make sure that if our linked list can perform certain things.
Traversing a single linked list
struct node *t;
t = head;
while(t != NULL) { // or while(t) have same meaning
printf("%d\n" , t->data);
t=t->next;
}
we are using t because if we lost the head , it's mean we lost the entire node.
Inserting an element in single linked list
struct node* new = (struct node*)malloc(sizeof(struct node))
this is will create a pointer called new
a) insert at beginning :
new->next=head;
head = new;
b) insert at the end
while(t->next != NULL) {
t=t->next;
}
t->next = new;
new->next = NULL;
c) insert a node at specific element
struct node
{
int i;
struct node *next;
}
// asume we need to insert after node 2
while(t->i != 2)
{
t = t->next;
}
new->next = t->next;
t->next = new;
Deleting a node from single linked list
malloc will create a space for us while free will free the memory that we got it from malloc
// assume we are resetting the linked list to it's init state
// deleting a node from the head
head = head->next;
free(t);
// deleting a node from the tail
while(t->next->next != NULL) {
t = t->next;
}
free(t->next);
t->next=NULL;
// delete a specific node
while(t->next->i != 3){
t = t->next;
}
struct node *t1 = t->next;
t->next = t1->next; // or t->next->next
free(t1);
example 1
struct node
{
int val;
struct node *next;
};
void rearrange(struct node *list)
{
struct node *p , *q;
int temp;
if(!list || !list->next) return; // if linkedlist have no or 1 element return
p = list; q=list->next; // q pointing to 1st element and q to second
while(q) // while q is not null do
{
temp = p->val;p->val=q->val;
q->val=temp;p=q->next; // swap q and p
q=p?p->next:0; // if p is pointing to something it will take it otherwise 0
}
}
// output : 2 1 4 3 6 5 7
printing the elements using recursion
// print then recursion
void f(struct node *p)
{
if(p)//1
{//2
printf("%d" , p->data);//3
f(p->link);//4
}//5
}
// output : 1 2 3 4
It will print before start go into next stack
when it's go back it will return to line 5
// recursion then print === print in reverse order
void f(struct node *p)
{
if(p)//1
{//2
f(p->link);//3
printf("$d" , p->data);//4
}//5
}
// output : 4 3 2 1
then when it go back it will start at line 4 which printing the value of p stored inside of each stack
Reversing an single linked list using iteration
struct node
{
int i;
struct node * next;
}
struct node * reverse(struct node * cur)
{
struct node *prev = NULL,*nextNode = NULL;
while(cur)
{
nextNode = cur->next;
cur->next=prev;
prev=cur;
cur=nextNode;
}
return prev;
}
Reversing an single linked list using recursion
struct node *head;
void reverse(struct node *prev , struct node *cur)
{
if(cur)
{
reverse(cur , cur->next);
cur->next = prev;
} else
head = prev;
}
void main()
{
//...
reverse(NULL , head);
//..
}
circular Linked List
circular linked list have it's tail pointing to sentinel which is the head but containing the number of nodes instead with pointer to first element.
while(p->next != head){}
double linked list
// insert at start
struct node {
int i;
struct node *prev;
struct node *next;
};
t->next = head;
head = t;
t->prev = NULL;
head->next->prev = head;
// insert at the end
while(p->next) p = p->next;
p->next=t;
t->prev=p;
t->next=NULL;
// insert between > 1 and < n where n is number of node
t->prev=p; // p is the pointer of the element previous to t
t->next=p->next;
p->next=t;
t->next->prev=t;
Top comments (0)