CODEWITHSUNDEEP
clinked-list
avinash
avinash

Reputation: 119

Can a structure be modified?

I have two separate linked lists which join together at some point and I have to find that point.I was thinking if I can add a new data type called visited(flag) so that I can make all the nodes of the first linked list as visited and then find the intersection point traversing from the second linked list.Can I do that?Can i modify a structure after defining it?If yes,how?Thanks in advance.

Upvotes: 0

Views: 110

Answers (4)

Alex Reynolds
Alex Reynolds

Reputation: 96966

Consider two sample lists A and B. You don't know where they intersect, but you have traversed both and you know their lengths:

A : A1 > A2 > A3 > A4 > NULL            <-- length 4
B : B1 > B2 > B3 > B4 > B5 > B6 > NULL  <-- length 6

If there's an intersection point, some memory address of Ai is going to equal to the memory address of Bj for 1 <= i <= 4 and 3 <= j <= 6.

Why?

If the address of A1 is equal to the address of B1 or B2 (if either of those nodes is the intersection point) then linked list A would really be two nodes or one node longer. But we know that's not true because we traversed A and we already know how long it is.

So what you can do is find the difference of lengths and walk that difference over the longer of the two lists — the intersection node, if it exists, will be in the tail of the longer list. Then start iterating through both lists, testing for pointer equality as you go:

# we know B is longer, but you would test this 
# condition and set up different code to handle 
# the two cases

unsigned int A_len = 4;
unsigned int B_len = 6;
unsigned int AB_diff = B_len - A_len; 
struct foo *A_head = ...; # user-defined
struct foo *B_head = ...; # user-defined
struct foo *A_iter = NULL;
struct foo *B_iter = NULL;

# - start the A-iterator at the first node of A
# - start the B-iterator at the diff-th node of B
#
# - now test for pointer equality until we find a 
#   match, or we hit the end of either list

for ( A_iter = A_head, B_iter = B_head + AB_diff; 
      (A_iter != B_iter) || (A_iter->nextNode != NULL); 
      ++A_iter, ++B_iter ) { }

# wherever A_iter and B_iter are now pointing will be 
# either NULL (if they don't intersect) or some non-NULL 
# value representing the intersection node

Upvotes: 3

Jim Balter
Jim Balter

Reputation: 16406

If the struct is defined in your source, you can simply add an additional member. If you have to work with a struct already defined in some library (or by your instructor), then no, you can't add members after the fact, but the next best thing is to maintain a hashtable that maps the address of struct instances to additional information about that struct. In this case, since the only information you need is whether the instance has been seen, just enter the addresses of the nodes of the first list into the hashtable, then scan the second list to see if any of its nodes are in the hashtable.

Also see the answer by Alex Reynolds that avoids the need for any additional information.

Upvotes: 0

sdn_world
sdn_world

Reputation: 353

No you cannot modify a structure after defining it. Why do you want to use data type only and why not any other method ?

However, what you can do is save the address of each Node of Linked List 1 in an array, and then use it find intersection point. This is close to what you want.

Again there are many better algorthims to find the intersection point which does not need of additional data type.

Upvotes: 0

David Grayson
David Grayson

Reputation: 87486

No, you cannot add or remove members from a struct at runtime.

Upvotes: 4

Related Questions