We do not fully understand the scope of human freedom, until we learn to let go.
User login
Two reference Single Linked List
An easier way to add elements to the end of a list (enqueue) without having to walkthrough all the list to find the last element is by keeping not only a reference to the head of the list (first element) but also to the tail of the list (last element).
Here is a proposal to the data structures needed for this purpose
struct Two_ref_list_node {
int val;
struct Two_ref_list_node *next;
};
typedef struct Two_ref_list_node node;
struct Two_ref_list_headers
{
node *head;
node *tail;
};
typedef struct Two_ref_list_headers headers;This reduces search time, but it also adds complexity to the algorithms as we need to make sure we update both reference correctly when we add nodes and specially when we remove nodes.
Another problem we still have is that we still need to look for the node located previous to the last node, but at least we don't have to look for the last node because we already have a reference to it (tail), so we are basically saving a search.
void enqueue(headers *list, int data)
{
node *curr = create_node(data);
if(!(list->tail))
{
list->head = list->tail = curr; //notice that when we are inserting the first node to the list, tail and head must point to the same node.
}
else
{
list->tail->next = curr;
list->tail = curr;
}
}
/* we still need this function to find the node previous to the last */
/* an interesting approach would be to have a third reference to the "previous-to-tail" node, but that will imply extra work in the algorithms to update the reference */
static node *previous_to_node(headers list, node *findee)
{
while(list.head)
{
if(list.head->next == findee)
return list.head;
list.head=list.head->next;
}
return list.head;
}
int dequeue(headers *list)
{
int ret = 0;
if(list->tail)
{
node *previous = previous_to_node(*list,list->tail);
ret = list->tail->val;
free(list->tail);
if(previous)
previous->next = NULL;
else
list->head = NULL;
list->tail = previous;
}
return ret;
}
- Log in to post comments