Sort linked list

Question

I have to read packets from a file, and reconstruct the packets into a linked list in order of the block_num.

struct packet {
    unsigned short  block_num;
    unsigned short  block_size;
    unsigned short  crc;
    unsigned char  *payload;
};

struct list {
    struct packet p;
    struct list *next;
};

This is my code for reading the packets and adding them into the linked list, but how would I sort them according to the block_num?

FILE *infp;

struct list *head = NULL;
struct list *last = NULL;

while (fread(&p, sizeof(p), 1, infp) != NULL) {
    packet *newpacket = malloc(sizeof(p));

    struct list *newlist = malloc(sizeof(list));
    newlist -> p = newpacket;
    newlist -> next = NULL;

    if (head == NULL) {
        head = last = newlist;
    } else {
        last -> next = newlist;
        last = newlist;
    }
}

@Smac89 No, he's not. Read the code. newList is a pointer to an instance of newList object, not the entire list. — Xephon, Feb 13 '14 at 23:01
Have you tried compiling the above code? There are quite a few errors in there that you should probably clean up first. For example the line `newlist -> p = newpacket` where `newpacket` is a pointer type, but `newlist->p` is not. — Eugene S, Feb 13 '14 at 23:05
If you collect all the packets and then sort them, an array is better than a linked list. If you want each packet inserted in the right place as they arrive, then you probably need to think about a (balanced) tree structure. The 'balanced' is important if, as is likely, the packets arrive more or less, but not completely, in order. Of the two, I'd probably use a dynamically growing array followed by `qsort()`. If you insist, you can make the array of `struct list` structures, and when the data is sorted, you can convert the array into a list. — Jonathan Leffler, Feb 14 '14 at 00:24

score 0 · Answer 1 · answered Feb 13 '14 at 23:10

0

You want the output to be a linked list whose member is sorted according to block_num. In this case, why not convert your read function to a smart reader.

The logic is as following:

If the list is empty, do as you normally do and assign head and last all to newList.
If the list is not empty, first look iterate through the list to find the position for the current object. Manipulate the list at that point and connect the node. For example:

`

for (cur = head; cur != end; cur = cur->next) {
    if (cur->p->block_num <= newpacket->block_num &&
        cur->next->p->block_num > newpacket->block_num) {
        // insert newlist here
        newlist->next = cur->next;
        cur->next = newlist;
    }
}

`

In above code, cur is of type struct list *.

answered Feb 13 '14 at 23:10

Xephon

393
1
12

This is a good first-stab kind of implementation, but I would add to the above that it has a bad worst-case runtime (if `block_num` increases with every packet read). A more efficient implementation (albeit more complex and may be overkill for this) would be to run some fast sorting algorithm (e.g., quick sort) after the entire file is read. – Eugene S Feb 13 '14 at 23:16
This is in fact insertion sort performed during reading, which is known to have time complexity of O(N^2). It is slow for larger inputs. A bigger problem is that your code does not handle corner cases. You should warn on that. – Palec Feb 13 '14 at 23:23
@unluddite Yes, the run-time is horrible. I'm just giving a direction to the OP. He should get to know how things can be done first then start profiling the code. This is when run-time is to be examined. – Xephon Feb 14 '14 at 14:26
@Palec I intentionally left out the boundary guard. As I stated, this is suppose to be a broad logic and an example as how things can be done during read. It is not insertion sort during reading but insertion sort itself. Also, I'm aware of the run time. See my other comment. – Xephon Feb 14 '14 at 14:28

score 0 · Answer 2 · answered Feb 13 '14 at 23:13

You have to implement your own sort as the standard qsort() works only on arrays. I recommend merge sort.

Also you can use an array instead of a linked list – then you could use qsort(). If you don’t know the number of packets you’ll read, just resize the array to be twice as big as previously each time it is full and you want to store another packet. Then the amortized time complexity of adding one item to the end is O(1).

score 0 · Answer 3 · answered Feb 14 '14 at 10:27

First of all you forgot to copy in the new element of the list what you read from the file, after the malloc, you should put:

*newpacket = p;

and you should declare newpacket outside of the while loop. Then the insertion in order in a linked list is done in this way (for lack of simplicity I only consider the block_num and I obtain it from the keyboard rather than from a file and stops when I press CTRL+D):

unsigned int block_num;
struct list *newlist;
struct list *x, *t;

while(scanf("%u", &block_num) == EOF) {
    newlist = (struct list *)malloc(sizeof(struct list));
    newlist->p.block_num = block_num;
    newlist->next = NULL;

    if(head == NULL) {
        /* empty list */
        head = newlist;
        last = newlist;
    }
    else {
        if(head->p.block_num > newlist->p.block_num) {
            /* insert as first element */
            newlist->next = head;
            head = newlist;
        }
        else {
            t = head;
            x = head->next;
            while(x != NULL && x->p.block_num < newlist->p.block_num) {
                t = x;
                x = x->next;
            }
            /* insert */
            t->next = newlist;
            newlist->next = x;
            if(x == NULL)
                last = newlist;
        }
    }
}

Sort linked list

3 Answers3