We do not fully understand the scope of human freedom, until we learn to let go.
User login
Double Linked List
This is yet another approach to the linked list problem. In this scenario we can walkthrough the list in any direction as each node has a reference not only to the next node but also to the previous node, thus reducing the search time during insertion at the cost of an extra data field (for the rear node reference) and more complex algorithms. The addition of two references as we did in the 2ref Single List eliminates completely the need for searching a node before insertion at the end of the list (tail).
This is an approach to the data structures required for Double Linked Lists with two reference headers:
struct list_node {
int val;
struct list_node *next;
struct list_node *rear;
};
typedef struct list_node node;
struct ref_list_headers
{
node *head;
node *tail;
};The algorithm complexity increase as we need to make sure that when we add a new node we need to make sure it is pointed backward by the node that was in the head or tail.
void push(headers *list, int data)
{
node *curr = create_node(data);
curr->next = list->head;
if(list->head)
{
printf("lista no vacia, agregando elemento al inicio %d, despues de %d\n",data,list->head->val);
list->head->rear=curr;
}
else
{
printf("lista vacia, agregando primer elemento %d\n",data);
list->tail = list->head;
}
list->head = curr;
if(!list->tail)
list->tail=curr;
}
int pop(headers *list)
{
if(list->head)
{
node *curr = list->head;
int temp = curr->val;
list->head = curr->next;
free(curr);
if(!(list->head))
list->tail = NULL;
return temp;
}
return 0;
}
void print_list(headers list)
{
node* curr;
for(curr=list.head;curr;curr=curr->next)
printf("%d\n", curr->val);
}
void print_list_reverse(headers list)
{
node* curr;
for(curr=list.tail;curr;curr=curr->rear)
printf("%d\n", curr->val);
}
void remove_head_node(headers *list)
{
if(list->head)
{
node *curr = list->head;
list->head = curr->next;
free(curr);
if(!list->head)
list->tail = NULL;
}
}
void delete_list(headers *list)
{
while(list->head)
remove_head_node(list);
}
void pop_all(headers *list)
{
while(list->head)
printf("%d\n", pop(list));
}
void enqueue(headers *list, int data)
{
node *curr = create_node(data);
if(!list->tail)
{
printf("lista vacia, agregando primer elemento %d\n",data);
list->head = list->tail = curr;
}
else
{
printf("lista no vacia, agregando elemento al final %d, despues de %d\n",data,list->tail->val);
curr->rear = list->tail;
list->tail->next = curr;
list->tail = curr;
}
}
- Log in to post comments