# Sorting a doubly linked list in C

Page 1 of 1

## 6 Replies - 19122 Views - Last Post: 09 February 2013 - 08:34 PMRate Topic: //<![CDATA[ rating = new ipb.rating( 'topic_rate_', { url: 'http://www.dreamincode.net/forums/index.php?app=forums&module=ajax&section=topics&do=rateTopic&t=311744&amp;s=5b1d8598dff5af20760924c687fd7360&md5check=' + ipb.vars['secure_hash'], cur_rating: 0, rated: 0, allow_rate: 0, multi_rate: 1, show_rate_text: true } ); //]]>

### #1 Drpogue

• New D.I.C Head

Reputation: 1
• Posts: 18
• Joined: 20-February 12

# Sorting a doubly linked list in C

Posted 09 February 2013 - 07:11 PM

So I've written a doubly linked list but when I got to the sort method I started to suffer from heavy derptation.

```#include<stdio.h>
#include<stdlib.h>
#include"list.h"
int i;
node *p;
node *n;

void insert(node *pointer, int data){
//go through list till ya find the last node
while(pointer->next!=NULL){
pointer = pointer->next;
}
//allocate memory for new node and put data in it
pointer->next = (node *)malloc(sizeof(node));
(pointer->next)->prev= pointer;
pointer = pointer->next;
pointer->data=data;
pointer->next = NULL;
}
void print(node *pointer){
if(pointer==NULL){
return;}
printf("%d ",pointer->data);
print(pointer->next);
}

int init(node *pointer,int find){
pointer =pointer->next;
while(pointer!=NULL){
if(pointer->data== find)//found find
{
printf("The data is in the list.");
return 1;
}
pointer = pointer->next;// Search in the next node.
}
printf("The data is not in the list.");
return 0;
}
void swap (node *x, node *y){
int temp= x->data;
x->data=y->data;
y->data=temp;
}
void sort(node *pointer){
for(i=0;i<10;i++){
if(pointer->data>pointer->next->data){
}else{
swap(pointer,pointer->next);
}
pointer=pointer->next;
}
}

int main(){
//new is used to point to the first node
//temp is for the last node
node *new, *temp;
int z;
new=(node *)malloc(sizeof(node));
temp= new;
temp ->next = NULL;
temp ->prev = NULL;

for(z=0;z<10;z++){
insert(new,(3*10)-z);
}
init(new,12);
init(new,3);
init(new,27);
init(new,7);
print(new);
sort(new);
print(new);

}

```

The code should print out a list of 30 29 28 27 26 25 24 23 22 21, then when the sort is working sort the list 21 22 23 24 25 26 27 28 29 30. But it just prints out the list twice in descending order. Where did I got wrong?

Is This A Good Question/Topic? 0

## Replies To: Sorting a doubly linked list in C

### #2 macosxnerd101

• Games, Graphs, and Auctions

Reputation: 11760
• Posts: 44,196
• Joined: 27-December 08

## Re: Sorting a doubly linked list in C

Posted 09 February 2013 - 07:54 PM

When dealing with Linked Lists, insertion sort or mergesort are really the algorithms you will want to implement. Bubblesort is expensive regularly, and algorithms that rely on lots of swaps become more inefficient when working with Linked Lists. Mergesort and Insertion Sort focus more on insertions than swaps. On top of that, when dealing with Linked Lists, mergesort doesn't require additional arrays when partitioning the List.

### #3 Drpogue

• New D.I.C Head

Reputation: 1
• Posts: 18
• Joined: 20-February 12

## Re: Sorting a doubly linked list in C

Posted 09 February 2013 - 08:01 PM

EDIT

This post has been edited by Drpogue: 09 February 2013 - 08:10 PM

### #4 macosxnerd101

• Games, Graphs, and Auctions

Reputation: 11760
• Posts: 44,196
• Joined: 27-December 08

## Re: Sorting a doubly linked list in C

Posted 09 February 2013 - 08:05 PM

I wouldn't describe this as a "Java" design. A bubblesort is a bubblesort, and it's fairly language agnostic. A note about spacing conventions though- you should work on them to make your code more legible.

Your algorithm really isn't a proper bubblesort. As baavgai advocates, it's not a bubblesort without a boolean. You also are missing the nested loops aspect.

Edit: Editing out your posts is a big no-no, by the way.

### #5 Drpogue

• New D.I.C Head

Reputation: 1
• Posts: 18
• Joined: 20-February 12

## Re: Sorting a doubly linked list in C

Posted 09 February 2013 - 08:14 PM

macosxnerd101, on 10 February 2013 - 03:05 AM, said:

I wouldn't describe this as a "Java" design. A bubblesort is a bubblesort, and it's fairly language agnostic. A note about spacing conventions though- you should work on them to make your code more legible.

Your algorithm really isn't a proper bubblesort. As baavgai advocates, [url=http://www.dreamincode.net/forums/topic/231304-the-real-bubble-sort/]it's not a bubblesort without a boolean[/url]. You also are missing the nested loops aspect.

Edit: Editing out your posts is a big no-no, by the way.

All I was saying is that I tried to follow plans in a different language and apply them in one I don't know.Thank you for debating the finer points of data structures with me.

### #6 macosxnerd101

• Games, Graphs, and Auctions

Reputation: 11760
• Posts: 44,196
• Joined: 27-December 08

## Re: Sorting a doubly linked list in C

Posted 09 February 2013 - 08:16 PM

Let's take a chill pill here. I'm not trying to berate you. I'm trying to get you going in the right direction. Your algorithm implementation is wrong, and I've told you why. I'm sorry that my help isn't appreciated.

### #7 Drpogue

• New D.I.C Head

Reputation: 1
• Posts: 18
• Joined: 20-February 12

## Re: Sorting a doubly linked list in C

Posted 09 February 2013 - 08:34 PM

I figured out the solution. Here is the code for any future users:

```#include<stdio.h>
#include<stdlib.h>
#include"list.h"
int i;
node *p;
node *n;

void insert(node *pointer, int data){
//go through list till ya find the last node
while(pointer->next!=NULL){
pointer = pointer->next;
}
//allocate memory for new node and put data in it
pointer->next = (node *)malloc(sizeof(node));
(pointer->next)->prev= pointer;
pointer = pointer->next;
pointer->data=data;
pointer->next = NULL;
}
void print(node *pointer){
if(pointer==NULL){
return;}
printf("%d ",pointer->data);
print(pointer->next);
}

int init(node *pointer,int find){
pointer =pointer->next;
while(pointer!=NULL){
if(pointer->data== find)//found find
{
printf("The data is in the list.");
return 1;
}
pointer = pointer->next;// Search in the next node.
}
printf("The data is not in the list.");
return 0;
}
void swap (node *x, node *y){
int temp= x->data;
x->data=y->data;
y->data=temp;
}
void sort(node*pointer){
int i;
while(pointer->next!=NULL){
if(pointer->data>pointer->next->data){
swap(pointer,pointer->next);
}
pointer=pointer->next;
sort(pointer);
}
}

int main(){
//new is used to point to the first node
//temp is for the last node
node *new, *temp;
int z;
new=(node *)malloc(sizeof(node));
temp= new;
temp ->next = NULL;
temp ->prev = NULL;

for(z=0;z<10;z++){
insert(new,(3*10)-z);
}
init(new,12);
init(new,3);
init(new,27);
init(new,7);
print(new);
sort(new);
print(new);

}

```