write two functions: insertNode and forwardTraverse, for an XOR linked list, a.k.a, memory efficient doubly linked list (DLL) in C PL. Ordinary DLLs requires space for two addresses (one pointing to previous node and one to next node). However, XOR LLs use bitwise XOR operation to save space for one address. Consider the below ordinary DLL.
write two functions: insertNode and forwardTraverse, for an XOR linked list, a.k.a, memory efficient doubly linked list (DLL) in C PL. Ordinary DLLs requires space for two addresses (one pointing to previous node and one to next node). However, XOR LLs use bitwise XOR operation to save space for one address. Consider the below ordinary DLL.
Database System Concepts
7th Edition
ISBN:9780078022159
Author:Abraham Silberschatz Professor, Henry F. Korth, S. Sudarshan
Publisher:Abraham Silberschatz Professor, Henry F. Korth, S. Sudarshan
Chapter1: Introduction
Section: Chapter Questions
Problem 1PE
Related questions
Question
write two functions: insertNode and forwardTraverse, for an XOR linked
list, a.k.a, memory efficient doubly linked list (DLL) in C PL. Ordinary DLLs requires space for two addresses
(one pointing to previous node and one to next node). However, XOR LLs use bitwise XOR operation to
save space for one address. Consider the below ordinary DLL.
Transcribed Image Text:startPtr
nextPtr
D null
null A
prevPtr
If you consider node B, prevPtr keeps the address of A, nextPtr keeps the address of C. Node A'a prevPtr
and node D's nextPtr keep NULL.
Now, let's name the address variable as npxor.
For node A, npxor = 0 XOR (address of B)
For node B, npxor = (address of A) XOR (address of C)
and so on.
Now remember bitwise XOR table:
bit a
bit b
a XOR b
1
1
Forward Traversal of XOR LL: While traversing the list we need to remember the address of the previously
accessed node in order to calculate the next node's address.
Remember this simple logic, e.g. for node C:
(address of B) XOR (npxor of C) = (address of D).
The reason is:
(address of B) XOR (address of D) = (npxor of C)
(npxor of C) XOR (address of B) = (address of B) XOR (address of D) XOR (address of B)
= (address of D) XOR O = (address of D)
Node Insertion into XOR LL: Insert the node in the beginning. As you remember from the course, the
head pointer should be manipulatable.
Given the related helper functions and node struct, fill the two empty functions.
Transcribed Image Text:#include <stdio.h>
#include <stdlib.h>
#include <inttypes.h>
struct Node
int data;
struct Node* npx;
};
struct Node* XOR (struct Node *a, struct Node *b)
return (struct Node*) ((uintptr_t) (a) ^ (uintptr_t) (b));
void insertNode(struct Node **headPtr, int data)
// Allocate memory for new node
/* Since new node is being inserted at the begining, npx of new node will always
be XOR of current head and NULL */
/* If linked list is not empty, then npx of current head node will be XOR
of new node and node next to current head */
// Change head
//FILL THIS FUNCTION
void forwardTraverse (struct Node *headPtr)
{
//FILL THIS FUNCTION
Expert Solution
This question has been solved!
Explore an expertly crafted, step-by-step solution for a thorough understanding of key concepts.
Step by step
Solved in 4 steps with 4 images
Knowledge Booster
Learn more about
Need a deep-dive on the concept behind this application? Look no further. Learn more about this topic, computer-science and related others by exploring similar questions and additional content below.Recommended textbooks for you
Database System Concepts
Computer Science
ISBN:
9780078022159
Author:
Abraham Silberschatz Professor, Henry F. Korth, S. Sudarshan
Publisher:
McGraw-Hill Education
Starting Out with Python (4th Edition)
Computer Science
ISBN:
9780134444321
Author:
Tony Gaddis
Publisher:
PEARSON
Digital Fundamentals (11th Edition)
Computer Science
ISBN:
9780132737968
Author:
Thomas L. Floyd
Publisher:
PEARSON
Database System Concepts
Computer Science
ISBN:
9780078022159
Author:
Abraham Silberschatz Professor, Henry F. Korth, S. Sudarshan
Publisher:
McGraw-Hill Education
Starting Out with Python (4th Edition)
Computer Science
ISBN:
9780134444321
Author:
Tony Gaddis
Publisher:
PEARSON
Digital Fundamentals (11th Edition)
Computer Science
ISBN:
9780132737968
Author:
Thomas L. Floyd
Publisher:
PEARSON
C How to Program (8th Edition)
Computer Science
ISBN:
9780133976892
Author:
Paul J. Deitel, Harvey Deitel
Publisher:
PEARSON
Database Systems: Design, Implementation, & Manag…
Computer Science
ISBN:
9781337627900
Author:
Carlos Coronel, Steven Morris
Publisher:
Cengage Learning
Programmable Logic Controllers
Computer Science
ISBN:
9780073373843
Author:
Frank D. Petruzella
Publisher:
McGraw-Hill Education