CODEWITHSUNDEEP
clinked-list
Ashish Rawat
Ashish Rawat

Reputation: 3513

How to compare linked list nodes?

GLib library done like this to compare two singly linked list nodes:

 typedef struct _GSList {
  _GSList *link;
   void *data;
} GSList;

    int g_sListPosition(GSList *list, GSList *llink) {
        int cnt = 0;
        while(list) {
            if(list == llink)  // Note here
                return cnt;
            cnt++;
            list = list->link;
        }

        return -1;
    }

But when I compare the nodes like this. It return false:

int main(void) {
    GSList *list = NULL, *list2 = NULL;
    list2 = g_sListAppend(list2, "def");
    list = g_sListAppend(list, "abc");
    list = g_sListAppend(list, "def");
    list = g_sListAppend(list, "ghi");
    printf("%d", g_sListPosition(list, list2));   // Return -1 ?
}

So, what's compare here (in the DOC, it's written gets the position of the given element in the GSList), a node or the data contained in the list ?

Edit: Thanks to all the given, my mistake I was actually doing it in wrong way. I have to compare same instance of the list.

Upvotes: 2

Views: 13697

Answers (3)

phoxis
phoxis

Reputation: 61910

The list with head list2

+--------+
|  def   |--->X
+--------+
   arr1

When the function allocates the node it will allocate a free memory location with the size of the node and then assign the string in the node's data part (where it has to assign the string).

The list with head list

+--------+    +--------+    +--------+
|   abc  |--->|   def  |--->|  ghi   |--->X
+--------+    +--------+    +--------+
   addr2         addr3         addr4

Here everytime you append a string to the linked list, a new node is allocated and the string is copied in the data part. Note that, everytime a new node is allocated the address of the node is different.

In the case above the first list with the data "def" has address addr1 and the second list has the node with data "def" has the address addr3 . So if you try to compare these two nodes with the == operator, naturally the comparison result will be false because the equality will compare the address of the nodes, which are different and thus return false.

If you want to particularly match a data in the node you need to compare it specifically. Which is, visit each node in list and compare the data part with the other node (list1).

On the other hand, if you to have exacted the node address inside a specific linked list, then you can use the address to compare. For example if you traverse the list till the end and get the address of the last node with "ghi" in it having address addr4, then you can use this address to compare that specific node inside the list later, provided that this node has not been freed and re-created with same data. In such case as you can see clearly even the data inside this node changes the address will remain the same.

Upvotes: 2

Grijesh Chauhan
Grijesh Chauhan

Reputation: 58271

Because list and llink are node address and we can't have two different nodes with same address, its very simple technique to find where llink start within in list(first).

Suppose list passes to function is like:

  //     0     1    2   3    4   
list---->[]-->[]-->[]-->[]-->[]---null
         23   42   18  102  324      

addresses are assumption

if llink value is 18, then function returns 2 because llink is third node in list.

and if llink not found it returns -1.

(like array index starts with 0 function count numbers node in list from 0)

As you commented I am commenting code:

    int cnt = 0;  // initial value of node_count is 0
    while(list) { // search while list not NULL (till end)
        if(list == llink) // if `llink` is a node in `list`
            return cnt;   // return node number  
        cnt++;   // else it may be next node
        list = list->link;
    }
    // control comes here if list == NULL, means llink not found

    return -1;  // not found so return -1
                // negative number can't be a position

comment:

I mean, how to test it If it really gives positive value

Call your function as below:

 g_sListPosition(list, list->link->link->link);
//                            0      1    2

it will return 2.

but note you list should be consists of 3 nodes.

Upvotes: 2

Ashish Rawat
Ashish Rawat

Reputation: 3513

I found that, we have to actually give the same instance of the list. Here's an example below:

int main(void) {
    RSList *list = NULL;
    list = r_sListAppend(list, "abc");
    list = r_sListAppend(list, "def");
    list = r_sListAppend(list, "ghi");

    RSList *list2 = list;
    int i = 2;
    while(i--) {
        list2 = list2->link;
    }
    printf("%d", r_sListIndexOf(list, list2));  // Print 2
}

Upvotes: 0

Related Questions