Im trying to shuffle a doubly linked list without changing it's pointers. So far my idea to do this is to have a position integer value that gets assigned randomly to each struct in the doubly linked list. I want to traverse the doubly linked list backwards and forwards in accordance to the order their position values were assigned.
Lets say the order of the position values in the list goes like 1,9,8,10,4,5,3,7,6,2. How would I traverse the doubly linkedlist so that I access 1,2,3,4... and so on in order?
Here is the struct:
typedef struct record{
char artist[50];
char albumTitle[50];
char songTitle[50];
char genre[50];
Duration songLength;
int timesPlayed;
int rating;
int position;
}Record;
Here is my node struct:
typedef struct node{
struct node *pPrev;
struct node *pNext;
Record record;
}Node;
Here is my attempt so far:
void shuffleRecords(Node *pList){
int recordAmount = countRecords(pList);
Node *pCurr = pList;
Record recordArr[recordAmount];
int assignedPositions[recordAmount];
int index=0;
Record tempRecord;
//initialize assigned positions
for(int i = 0; i < recordAmount; i++){
assignedPositions[i] = 0;
}
while(pCurr != NULL){
recordArr[index] = pCurr->record;
index++;
pCurr=pCurr->pNext;
}
for(int i = 0; i < recordAmount;i++){
int newPosition;
do{
newPosition = rand() % recordAmount + 1;
}while(assignedPositions[newPosition-1] == 1);
recordArr[i].position = newPosition;
assignedPositions[newPosition-1] = 1;
printf("%s|%s|%s|%s|%d:%d|%d|%d POSITION: %d\n",recordArr[i].artist,recordArr[i].albumTitle,
recordArr[i].songTitle,recordArr[i].genre,
recordArr[i].songLength.minutes,recordArr[i].songLength.seconds,
recordArr[i].timesPlayed,recordArr[i].rating,recordArr[i].position);
}
for(int i = 0; i < recordAmount;i++){
Node *pTraverse=pList;
int traverseIndex = i+1;
if(traverseIndex % 2 == 0){//traverse forwards
while(pTraverse != NULL && pTraverse->record.position != traverseIndex){
pTraverse=pTraverse->pNext;
}
}else{//traverse backwards
while(pTraverse != NULL && pTraverse->record.position != traverseIndex){
pTraverse=pTraverse->pPrev;
}
}
if (pTraverse != NULL){
printf("%s\n",pTraverse->record.songTitle);
}
}
}
Here is an example of the position values:
Brooks, Garth|FRESH HORSES|The Old Stuff|Country|2:57|11|2 POSITION: 8
Swift, Taylor|RED|Stay Stay Stay|Pop|4:42|5|1 POSITION: 1
Adele|25|Remedy|Pop|4:11|24|4 POSITION: 4
Eminem|SHADYXV|Vegas|Rap|3:37|8|3 POSITION: 7
Bieber, Justin|PURPOSE|No Sense|Pop|4:12|6|1 POSITION: 5
Perri, Christina|HEAD OF HEART|Trust|Pop|2:35|3|5 POSITION: 3
Drake|YOU WELCOME|The Motto|Rap|4:13|7|4 POSITION: 9
Drake|NOTHING WAS THE SAME|Own it|Rap|3:23|3|3 POSITION: 2
Swift, Taylor|1989|Shake it Off|Pop|3:35|12|3 POSITION: 6
If you define a few functions to create nodes, get the length of a list, and get a node at a specific index, this is made fairly straightforward.
A simplified example with just an int in each node, and a singly-linked list, but you should be able to extrapolate the logic. Caveat: this scales poorly as it is an O(n^2) algorithm for a linked list. For large sample sizes, you'd be better off converting to and from arrays which have constant-time access based on index.
Result: