Re: [algogeeks] Double Linked List Represented With Single Linked List
These posts will clear ur questions http://www.geeksforgeeks.org/archives/12367 http://www.geeksforgeeks.org/archives/12615 -- ATul Singh | Computer Science Engineering| 2008-12 Batch | NIT Jalandhar | 9530739855 -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Double Linked List Represented With Single Linked List
Krishna, how can you store a address pointing to k bits value into k/2 bits? XOR is the way to do this. -- Amitesh On Thu, Jun 21, 2012 at 1:20 AM, Krishna Kishore kknarenkris...@gmail.comwrote: *np *is nothing but *next_pointer. np[x] *does mean *x-np *which is the next pointer to node. Actually I am thinking in this way about *np, *that it stores the *XOR* value of *next* and *prev* pointers.Or Since *np *is a k-bit integer, the first k/2 bits wil be used for *next*, and other k/2 bits wil be used for *prev *pointer. On Wednesday, 20 June 2012 18:28:07 UTC+5:30, adarsh kumar wrote: Simple! Just traverse the doubly linked list and keep track of next and previous of each node, and do XOR and save the result in a new pointer, what according to you is np. Be careful about boundary cases, i.e head and tail, though. On Wed, Jun 20, 2012 at 5:16 PM, Krishna Kishore kknarenkris...@gmail.com wrote: Explain how to implement doubly linked lists using only one pointer value * np[x*] per item instead of the usual two (next and prev). Assume that all pointer values can be interpreted as k-bit integers, and define* np[x] to be np[x] = next[x] XOR prev[x],*the k-bit “exclusive-or” of next[x] and prev[x]. (The value NIL is represented by 0.) Be sure to describe what information is needed to access the head of the list. Show how to implement the SEARCH, INSERT, and DELETE operations on such a list. Also show how to reverse such a list in O(1) time. This is the Question in the Book *Introduction To Algorithms *By CORMEN ( MIT Press ) Page Number : 209 , Problem No: 10.2-8. Thanks in Advance. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To view this discussion on the web visit https://groups.google.com/d/** msg/algogeeks/-/Uj1E8KXljAQJhttps://groups.google.com/d/msg/algogeeks/-/Uj1E8KXljAQJ . To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscribe@** googlegroups.com algogeeks%2bunsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/** group/algogeeks?hl=en http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To view this discussion on the web visit https://groups.google.com/d/msg/algogeeks/-/JlNBCRsj9kUJ. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Double Linked List Represented With Single Linked List
Explain how to implement doubly linked lists using only one pointer value*np[x *] per item instead of the usual two (next and prev). Assume that all pointer values can be interpreted as k-bit integers, and define* np[x] to be np[x] = next[x] XOR prev[x],* the k-bit “exclusive-or” of next[x] and prev[x]. (The value NIL is represented by 0.) Be sure to describe what information is needed to access the head of the list. Show how to implement the SEARCH, INSERT, and DELETE operations on such a list. Also show how to reverse such a list in O(1) time. This is the Question in the Book *Introduction To Algorithms *By CORMEN ( MIT Press ) Page Number : 209 , Problem No: 10.2-8. Thanks in Advance. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To view this discussion on the web visit https://groups.google.com/d/msg/algogeeks/-/Uj1E8KXljAQJ. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Double Linked List Represented With Single Linked List
Simple! Just traverse the doubly linked list and keep track of next and previous of each node, and do XOR and save the result in a new pointer, what according to you is np. Be careful about boundary cases, i.e head and tail, though. On Wed, Jun 20, 2012 at 5:16 PM, Krishna Kishore kknarenkris...@gmail.comwrote: Explain how to implement doubly linked lists using only one pointer value*np[x *] per item instead of the usual two (next and prev). Assume that all pointer values can be interpreted as k-bit integers, and define* np[x] to be np[x] = next[x] XOR prev[x],* the k-bit “exclusive-or” of next[x] and prev[x]. (The value NIL is represented by 0.) Be sure to describe what information is needed to access the head of the list. Show how to implement the SEARCH, INSERT, and DELETE operations on such a list. Also show how to reverse such a list in O(1) time. This is the Question in the Book *Introduction To Algorithms *By CORMEN ( MIT Press ) Page Number : 209 , Problem No: 10.2-8. Thanks in Advance. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To view this discussion on the web visit https://groups.google.com/d/msg/algogeeks/-/Uj1E8KXljAQJ. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Double Linked List Represented With Single Linked List
*np *is nothing but *next_pointer. np[x] *does mean *x-np *which is the next pointer to node. Actually I am thinking in this way about *np, *that it stores the *XOR* value of *next* and *prev* pointers.Or Since *np *is a k-bit integer, the first k/2 bits wil be used for *next*, and other k/2 bits wil be used for *prev *pointer. On Wednesday, 20 June 2012 18:28:07 UTC+5:30, adarsh kumar wrote: Simple! Just traverse the doubly linked list and keep track of next and previous of each node, and do XOR and save the result in a new pointer, what according to you is np. Be careful about boundary cases, i.e head and tail, though. On Wed, Jun 20, 2012 at 5:16 PM, Krishna Kishore kknarenkris...@gmail.com wrote: Explain how to implement doubly linked lists using only one pointer value * np[x*] per item instead of the usual two (next and prev). Assume that all pointer values can be interpreted as k-bit integers, and define* np[x] to be np[x] = next[x] XOR prev[x],*the k-bit “exclusive-or” of next[x] and prev[x]. (The value NIL is represented by 0.) Be sure to describe what information is needed to access the head of the list. Show how to implement the SEARCH, INSERT, and DELETE operations on such a list. Also show how to reverse such a list in O(1) time. This is the Question in the Book *Introduction To Algorithms *By CORMEN ( MIT Press ) Page Number : 209 , Problem No: 10.2-8. Thanks in Advance. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To view this discussion on the web visit https://groups.google.com/d/msg/algogeeks/-/Uj1E8KXljAQJ. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To view this discussion on the web visit https://groups.google.com/d/msg/algogeeks/-/JlNBCRsj9kUJ. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
