1 Replies - 352 Views - Last Post: 11 December 2012 - 11:10 AM Rate Topic: -----

#1 emk0  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 6
  • Joined: 08-September 12

Sorted insert into Linked List (Iterative)

Posted 11 December 2012 - 09:52 AM

I have been working with this iterative function since Sunday without any success, I want to create iterative function for sorted insert but after hours of node drawings, I think i would need some help with the function:
struct declaration:
  typedef struct E_Type * List;

  struct E_Type
  {
      int data;
      struct E_Type* next;
  };


and the function:

bool insert(List & l, int data) {
    while (l != 0) {
        for (List p = l; p; p = p->next) {
            if (p->data == data)
                return false;
        }

        if (l->data > data) {
            List new_list = new E_Type;
            new_list->data = data;
            new_list->next = l;
            l = new_list;
            return true;
        } else if (l->data < data) {

            List new_list = new E_Type;
            new_list->data = data;
            l->next = new_list;
            l = new_list;
            return true;
        }
    }

    if (l == 0) {
        List new_list = new E_Type;
        new_list->data = data;
        new_list->next = l;
        l = new_list;
        return true;
    }
}






i have been working with this iterative function since Sunday without any success, I want to create iterative function for sorted insert but after hour of node drawings, I think i would need some help with the function:

struct declaration:

  typedef struct E_Type * List;

  struct E_Type
  {
      int data;
      struct E_Type* next;
  };

the function:

bool insert(List & l, int data) {
    while (l != 0) {
        for (List p = l; p; p = p->next) {
            if (p->data == data)
                return false;
        }

        if (l->data > data) {
            List new_list = new E_Type;
            new_list->data = data;
            new_list->next = l;
            l = new_list;
            return true;
        } else if (l->data < data) {

            List new_list = new E_Type;
            new_list->data = data;
            l->next = new_list;
            l = new_list;
            return true;
        }
    }

    if (l == 0) {
        List new_list = new E_Type;
        new_list->data = data;
        new_list->next = l;
        l = new_list;
        return true;
    }
}


btw: is this function even possible... all tutorials, guides .. etc about this insertion are with recursive call for next-data < data

This post has been edited by jimblumberg: 11 December 2012 - 10:20 AM
Reason for edit:: Added missing Code Tags, Please learn to use them.


Is This A Good Question/Topic? 0
  • +

Replies To: Sorted insert into Linked List (Iterative)

#2 baavgai  Icon User is offline

  • Dreaming Coder
  • member icon

Reputation: 5777
  • View blog
  • Posts: 12,591
  • Joined: 16-October 07

Re: Sorted insert into Linked List (Iterative)

Posted 11 December 2012 - 11:10 AM

A few things. Hiding pointers is bad. E_Type is a wonky kind of name for a node. You're using C++, your node should have a constructor. Your list should be an class.

If nothing else, write some creation code for your node:
E_Type *createNode(int data, E_Type *next) {
	E_Type *node = new E_Type;
	node->data = data;
	node->next = next;
	return node;
}



Though, it would be vastly better as:
struct E_Type {
	int data;
	E_Type *next;
	E_Type(int d, E_Type *n) : data(d), next(n) { }
};



That for loop in your insert is pointless. Also, checking for data > l->data isn't all that helpful.

There are three cases you need consider:
If the list is empty, just create a node.
If the data is < the data in the current head, replace the current head with a new node pointing to the old head.
Otherwise, search for a place to put a new node. You must loop based on the prior node, so you can attach it's next to the new node. If you reach the end of the list, you attach the new node to then end.

Recursive insert? For a linked list? Not usually. For a tree, but not a list.
Was This Post Helpful? 0
  • +
  • -

Page 1 of 1