Pointers - double linked list - HELP

[claudilla]

Write your question here.

  typedef struct TCBlock *TCBptr; //pointer that points to the struct??

typedef struct TCBlock {				
    int	TCBId;			/* Task name or ID*/    
    char state;			/* current state */
    int priority;		/* current priority */
    TCBptr next;		/* forward ptr for double linked list */
    TCBptr prev;       /* prev otr for double linked lsit*/
}  TCB;

void YKNewTask(void (* task)(void), void *taskStack, unsigned char priority){
    
    TCBptr currTCB, nextTCB;
    /* code to grab an unused TCB from the available list */??
    currTCB = emptyTCBList;              /*putting first task to temp*/???
    emptyTCBList = currTCB->next;
    
    if (readyTCBList == NULL)	/* is this first insertion, checking for first time???? */
    {
        readyTCBList = currTCB; //CURRENT TCB
        newTCB->next = NULL;
        newTCB->prev = NULL;
    }
    else			/* not first insertion */
    {
        nextTCB = readyTCBList;	????
        while (nextTCB->priority < currTCB->priority)
            nextTCB = nextTCB->next;	/???
        if (nextTCB->prev == NULL)	??
            readyTCBList = currTCB;
        else
            nextTCB->prev->next = currTCB;
        currTCB->prev = nextTCB->prev;
        currTCB->next = nextTCB;
        nextTCB->prev = currTCB;
    }
}

I'm trying to understand this double linked list. I'm really confused with some part. For example line 15, is emptyTCBList pointing to currentTCB??
In line 16, is the next element of currTCB pointing to empty List?
I don't get this line nextTCB->prev->next = currTCB??
I have 4 pointers. Does the 4 pointer point to its individual struct?

[Nico]

What do you think is happening?
Do you understand a regular/single linked list?
In other words, what do you already grasp and where do things get unclear?

[claudilla]

I watched videos of a regular linked list. A double linked list has a node* prev. There are a few things are unclear for me.
For example when you declare a pointer ex. currTCB. This currTCB holds the members defined in the struct. but does that mean that currTCB points the struct right? So when we set currTCB = emptyTCBList... does that mean that the pointer doesn't point to currTCB and now points to a the struct of emptyTCBList?

[claudilla]

Any help guys?

[SakurasouBusters]

Is it not an assignment, you are learning it by your own?

[claudilla]

Yeah...,What is it then?

[claudilla]

What do you mean it is not an assignment. Pointers point to an struct... they only point , right?

[Nico]

Hello,

I am afraid I can not answer all your questions, but I hope I can help a bit.
From the top:
typedef struct TCBlock *TCBptr;
The astrix before the pointer gives you the object that the pointer points to (instead of the pointer).

currTCB = emptyTCBList; /*putting first task to temp*/???
I am not sure, but it seems like a pointer to the first empty spot in the list (equal to dubble_linked_list_back in the exmple below).

if (readyTCBList == NULL) /* is this first insertion, checking for first time???? */
Yes, when you add/remove the first node of a list you have to do some other things as for all subsequent nodes.

nextTCB = readyTCBList;
readyTCBList is the pointer to the first node in the list (equal to dubble_linked_list_front in the example below).

while (nextTCB->priority < currTCB->priority) nextTCB = nextTCB->next;
When they insert a new task in the list they don't insert it at the end, they keep the tasks ordered based on their priority. Because of this inserting a new task (new node) in the list requires you to first find the last task that is in the (ordered) list with a lower priority than the new task, so that you can insert the new task directly after it.
What they do here is checking every node from the start of the list to the end of the list, until they found the correct position for the new node.

Now this is a point where I get confused, because I would expect them to compare with the priority parameter from the function call. In fact none of the function arguments seem to be used. I think this may be a bug, but it could also be because the code that you posted is not complete.

if (nextTCB->prev == NULL) ??
Similar to adding the first node, inserting a node before the first node must be done slightly different from inserting a node on any other place. So before you start to insert you must check if the position where you should insert just happens to be in front of the first node. The first node can be recognized in two ways:
1. the pointer to the start of the list points to it.
2. it is the only node in the list that does not have a previous node.


I have made the example code below in an attempt to clarify the working of a linked list in general (I hope without confusing names). In this example I add nodes to the list, walk through the list in two directions and remove a node. Inserting a node should be comparable to deleting one (but in reverse obviously).

#include <iostream>

struct Node
{
    int	some_thing_to_link;
    Node* next;		    /* forward ptr for double linked list */
    Node* prev;         /* prev otr for double linked lsit*/
};

Node* dubble_linked_list_front = nullptr;
Node* dubble_linked_list_back = nullptr;


void addNodeToList(int node_content)
{
    // Create the Node
    Node* a_new_node = new Node();
    a_new_node->some_thing_to_link = node_content;
    a_new_node->next = nullptr;
    a_new_node->prev = dubble_linked_list_back;
    // Insert the new node to the list
    if (dubble_linked_list_front == nullptr)        // If the list is still empty, we have to do a bit more
    {
        dubble_linked_list_front = a_new_node;      // The front of the list is linked
        dubble_linked_list_back = a_new_node;       // The new node is initially the end of the list
    }
    else
    {
        dubble_linked_list_back->next = a_new_node;  // Link the last node in the list to the new node
        dubble_linked_list_back = a_new_node;       // Update the pointer to the new last end of the list
    }
}

void removeFromList(Node* node_to_remove_from_list)
{
    std::cout << "Going to remove the node with value " << node_to_remove_from_list->some_thing_to_link << std::endl << std::endl;
    if (node_to_remove_from_list->prev == nullptr)  // This happens to be the first node in the list
    {
        dubble_linked_list_front = node_to_remove_from_list->next; // This may be a nullptr, but that is ok.
    }
    else
    {
        (node_to_remove_from_list->prev)->next = node_to_remove_from_list->next;    // link the previous node to the next
        (node_to_remove_from_list->next)->prev = node_to_remove_from_list->prev;    // link the next node to the previous
        delete node_to_remove_from_list;   // Free the memory now that the object is not connected in anyway anymore
    }
}

void printList()
{
    Node* current_node = dubble_linked_list_front;  // We copy the pointer to make sure we won't change the list by accident
    while (current_node != nullptr)                 // The next pointer of the last node is a nullptr
    {
        std::cout << "Node with value " << current_node->some_thing_to_link << std::endl;
        current_node = current_node->next;
    }
    std::cout << "End of the list was reached." << std::endl << std::endl;

    // Now lets print it in reverse order (easy with a double linked list)
    current_node = dubble_linked_list_back;
    while (current_node != nullptr)                 // The prev pointer of the first node is a nullprt
    {
        std::cout << "Node with value " << current_node->some_thing_to_link << std::endl;
        current_node = current_node->prev;
    }
    std::cout << "Front of the list was reached." << std::endl << std::endl;
}

int main ()
{
    // The empty list is just a pointer to the start and the end of the list.
    // =>null
    // null<=

    // We start by inserting some stuff into the list.
    addNodeToList(1);
    // =>1<=
    addNodeToList(2);
    // =>1<=>2<=
    addNodeToList(3);
    // =>1<=>2<=>3<=
    addNodeToList(4);
    // =>1<=>2<=>3<=>4<=
    addNodeToList(5);
    // =>1<=>2<=>3<=>4<=>5<=

    // Let us see what we have created
    printList();

    // Now we remove a node from the list
    removeFromList(dubble_linked_list_front->next); // remove the second node from the list
    // =>1<=>2<=>3<=>4<=>5<= becomes    =>1 =>3<=>4<=>5<=
    //                                    2<=>3
    // =>1=>3<=>4<=>5<=      becomes    =>1<=>3<=>4<=>5<=
    //   2<=3                             2

    // Let us see what changed
    printList();
}