Splitting a linked list
Why are the section lists always empty in this program? (It is derived from code on the Wikipedia page on linked lists.)
/*
Example program from wikipedia linked list article
Modified to find nth node and to split the list
*/
#include <stdio.h>
#include <stdlib.h>
typedef struct ns
{
int data;
struct ns *next; /* pointer to next element in list */
} node;
node *list_add(node **p, int i)
{
node *n = (node *)malloc(sizeof(node));
if (n == NULL)
return NULL;
n->next = *p; //* the previous element (*p) now becomes the "next" element */
*p = n; //* add new empty element to the front (head) of the list */
n->data = i;
return *p;
}
void list_print(node *n)
{
int i=0;
if (n == NULL)
{
printf("list is empty\n");
}
while (n != NULL)
{
printf("Value at node #%d = %d\n", i, n->data);
n = n->next;
i++;
}
}
node *list_nth(node *head, int index) {
node *current = head;
node *temp=NULL;
int count = 0; // the index of the node we're currently looking at
while (current != NULL) {
if (count == index)
temp = current;
count++;
current = current->next;
}
return temp;
}
/*
This function is to split a linked list:
Return a list with nodes starting from index 'int ind' and
step the index by 'int step' until the end of list.
*/
node *list_split(node *head, int ind, int step) {
node *current = head;
node *temp=NULL;
int count = ind; // the index of the node we're currently looking at
temp = list_nth(current, ind);
while (current != NULL) {
count = count+step;
temp->next = list_nth(head, count);
current = current->next;
}
return temp; /* return the final stepped list */
}
int main(void)
{
node *n = NULL, *list1=NULL, *list2=NULL, *list3=NULL, *list4=NULL;
int i;
/* List with 30 nodes */
for(i=0;i<=30;i++){
list_add(&n, i);
}
list_print(n);
/* Get 1th, 5th, 9th, 13th, 18th ... nodes of n etc */
list1 = list_split(n, 1, 4);
list_print(list1);
list2 = list_split(n, 2, 4); /* 2, 6, 10, 14 etc */
list_print(list2);
list3 = list_split(n, 3, 4); /* 3, 7, 11, 15 etc */
list_print(list3);
list3 = list_split(n, 4, 4); /* 4, 8, 12, 16 etc */
list_print(list4);
getch();
return 0;
}
temp = list_nth(current, ind);
while (current != NULL) {
count = count+step;
temp->next = list_nth(head, count);
current = current->next;
}
You find the right element to start splitting, but see what happens to the tempo then ... you only assign temp-> next.
You need to keep track of both the header of your split list and the tail where you insert new elements.
source to share
In fact, the program has more than one problem.
-
Indexes are not the native way of addressing the contents of linked lists. Usually, pointers to nodes or iterators (which are masked pointers to nodes) are used. With indexes, node access has linear complexity (
O(n)
) instead of constantO(1)
. -
Note that this
list_nth
returns a pointer to a live node in the list, not a copy. By assigningtemp->next
tolist_split
, you are overwriting the original list instead of creating a new (but perhaps intentional?) -
The inside
list_split
temp
never progresses, so the loop just snaps the nodes to the head, not the tail. -
Due to its use
list_nth
to find nodes by iterating over the entire list from the beginning,list_split
has quadratic time (O(n**2)
) instead of linear time. Better to rewrite the function to iterate over the list once and copy (or reattach) the required nodes as you go through them instead of calling themlist_nth
. Or you can writecurrent = list_nth(current, step)
. -
[EDIT] Forgot to mention. Since you are rewinding the original list, the notation
list_nth(head, count)
is wrong: it will move through the short circus list rather than the unchanged one.
source to share
Your description of what list_split should return is pretty clear, but it's not clear what should happen, if anything, in the original list. Assuming this shouldn't change:
node *list_split(node *head, int ind, int step) {
node *current = head;
node *newlist=NULL;
node **end = &newlist;
node *temp = list_nth(current, ind);
while (temp != NULL) {
*end = (node *)malloc(sizeof(node));
if (*end == NULL) return NULL;
(*end)->data = temp->data;
end = &((*end)->next);
temp = list_nth(temp, step);
}
return newlist; /* return the final stepped list */
}
(You probably want to include the list_insert routine from what inserts a new node at a specific location. List_add is not very useful as it always adds the beginning of the list.)
source to share