C: Auto sorting double linked list

[M_D_K]

This is just a little something for ultimatedragoon6 (to show how overcomplicated his implementation was), but I figured I'd share.

Code: Select all

//Simple implementation of an auto sorting double linked list
//compile with gcc -Wall -o sorted_link sorted_linked.c
//Placing this in the public domain since there is nothing original in it ;)
#include <stdlib.h>
#include <stdio.h>

struct Node
{
	struct Node *next;
	struct Node *prev;
	int id;
};

struct Node *CreateList(int id)
{
	struct Node *list = (struct Node *)malloc(sizeof(struct Node));
	list->prev = NULL; //this makes list root
	list->next = NULL;
	list->id = id;
	return list;
};

//Good ol' recursion :)
void DeleteList(struct Node *node)
{
	if(node->next != NULL)
		DeleteList(node->next);

	free(node);
};

void DumpList(struct Node *list)
{
	printf("list node: id -> %d\n", list->id);
	if(list->next != NULL)
		DumpList(list->next);
};

struct Node *PushToFront(struct Node *root, int id)
{
	struct Node *newNode = (struct Node *)malloc(sizeof(struct Node));
	newNode->prev = NULL;
	newNode->next = root;
	newNode->id = id;
	root->prev = newNode;
	return newNode;
};

struct Node *PushToBack(struct Node *root, int id)
{
	struct Node *newNode = (struct Node*)malloc(sizeof(struct Node));
	newNode->next = NULL;
	newNode->id = id;
	struct Node *temp = root;

	while(temp->next != NULL)
		temp = temp->next;

	temp->next = newNode;
	newNode->prev = temp;
	return root;
};

struct Node *Insert(struct Node *root, int id)
{
	struct Node *temp = root;
	int lowerID = root->id;
	struct Node *insert = NULL;

	while(temp->next != NULL)
	{
		if(temp->id <= id && temp->id >= lowerID)
		{
			lowerID = temp->id;
			insert = temp;
		}

		if(temp->id > id && temp->id > lowerID) //HAS to be greater than only
			break; //gone too far

		temp = temp->next;
	}

	//we're at the end and no sign of a bigger id so just stick it on the back :)
	if(temp->id <= id)
		return PushToBack(root, id);

	//if this is the only node
	if(insert == NULL)
	{
		if(id <= root->id)
			return PushToFront(root, id);
		else
			return PushToBack(root, id);
	}

	if(insert->next->id > id)
	{
		struct Node *newNode = (struct Node*)malloc(sizeof(struct Node));
		newNode->id = id;
		newNode->prev = insert;
		newNode->next = insert->next;
		insert->next = newNode;
		newNode->next->prev = newNode;
	}
	return root;
};

int main(int argc, char *argv[])
{
	if(argc <= 1)
	{
		printf("no arguments given\nExample:\n\tsorted_link 2 4 3 6 8 200 120\n");
		exit(0);
	}
	struct Node *list = CreateList(atoi(argv[1]));
	printf("created list\n");
	printf("adding items\n");
	int i;
	for(i = 2; i < argc; i++)
	{
		list = Insert(list, atoi(argv[i]));
		putchar('.');
	}
	putchar('\n');
	DumpList(list);
	DeleteList(list);
	return 0;
};

[ultimatedragoon69]

well, i've looked over your code. i'm rather baffled that mine is as overcomplicated as it is. I'm going to rework my formula's and shrink my code.
Thanks.

[Ginto8]

pretty cool stuff.
However, I did notice an unnecessary assignment (this is just me nitpicking):

Code: Select all

list = Insert(list, atoi(argv[i]));

can just be

Code: Select all

Insert(list, atoi(argv[i]));

since there is no change in the pointer to the list, the assignment is unnecessary.
that's just my 2 cents

[M_D_K]

no it can't, if Insert is inserting at the front of the list, you'd need to update list with the new root node.

There is a method to this madness.

[Ginto8]

no it can't, if Insert is inserting at the front of the list, you'd need to update list with the new root node.

There is a method to this madness.

OH. oops, didn't look closely enough at PushToFront()

Code: Select all

return newNode;

sorry about that

[avansc]

Something a little different with same result.
header

Code: Select all

/*
 *  avs_List.h
 *  linked_list
 *
 *  Created by Andre van-Schalkwyk on 3/30/10.
 *  Copyright 2010 N/A. All rights reserved.
 *
 */

#ifndef _avs_List_h
#define _avs_List_h

class avs_List
{
public:
	avs_List();
	void add(const int n);
	void print();
private:
	int *list;
	int len;
};

#endif;

Source

Code: Select all

/*
 *  avs_List.cpp
 *  linked_list
 *
 *  Created by Andre van-Schalkwyk on 3/30/10.
 *  Copyright 2010 N/A. All rights reserved.
 *
 */

#include <stdlib.h>
#include <stdio.h>
#include <string.h>

#include "avs_List.h"

avs_List::avs_List()
{
	this->len = 0;
	this->list = NULL;
}

void avs_List::add(const int n)
{	
	int *nList = (int*)malloc(sizeof(int)*this->len+1);
	
	for(unsigned int a = 0;a < this->len;a++)
	{
		if(n < this->list[a])
		{
			memmove(nList, this->list, a*sizeof(int));
			nList[a] = n;
			memmove(nList+a+1, this->list+a, (this->len-a)*sizeof(int));
			this->len++;
			free(this->list);
			this->list = nList;
			return;
		}
	}
	 
	memmove(nList, this->list, this->len*sizeof(int));
	nList[this->len] = n;
	this->len++;
	free(this->list);
	this->list = nList;
}

void avs_List::print()
{
	for(unsigned int a = 0;a < this->len;a++)
		printf("%d\n", this->list[a]);
}

[Jaus]

I think avansc won, just due to the fact that that is post # 1337

[Ginto8]

attaching proof for the ages

[dandymcgee]

Not really proof, technically all of his posts say that right now.

[eatcomics]

they won't when he posts again... But avan wins, cause he's avan...

[ultimatedragoon69]

I just wanted to post my insert function now that it's done.

Code: Select all

template <class DATA>
void LHandler<DATA>::insert(DATA newData)
{
    LNode<DATA>* current = head;

    if(current = NULL)
    {
        pushToFront(newData);
    }
    for(current = head; current != NULL; current = current->getNext())
    {
        if(newData >= current->getData() && newData <= current->getNext()->getData())
        {
            LNode<DATA>* newNode = new LNode<DATA>(newData);
            newNode->setNext(current->getNext());
            newNode->setPrevious(current);
            current->getNext()->setPrevious(newNode);
            current->setNext(newNode);
            nodeCount++;
            break;
        }
        else if(newData <= head->getData())
        {
            pushToFront(newData);
            break;
        }
        else if(newData >= tail->getData())
        {
            pushToBack(newData);
            break;
        }
    }
}