C++

Forum

 
Insert into a sorted singly linked list

ande6870 (13)
I was wondering if anyone could provide a quick easy tutorial on how to insert things into a sorted singly linked list. i am an amateur programmer learning most of this on my own.

i want to start with an empty singly linked list and when i insert items into it they will be inserted in sorted order.

this is my struct i am using

1
2
3
4
5
6
 
struct Node
  {
    int packet;
    string data;
    Node *link;
  };


the items are sorted by the packet number which is the first item in the struct.
Kenneth7 (3)
closed account (D80DSL3A)
Assuming you have a list class like the following:
1
2
3
4
5
6
7
8
 
class list
{
    public:
    Node* head;
    list(): head(NULL) {}// ctor
    void insert( int Packet, string Data );
    // other functions
};


The basic idea with the insert() is this:
If head == NULL there are no Nodes yet. Add the 1st Node as the head.
Otherwise, compare Packet to head->packet:

if( Packet < head->packet ) insert the new node before the head (like push_front() ).
else iterate through the list until iter->link->data < Packet is false or iter->link == NULL.
In my own function this looks like:
1
2
3
 
Node *iter = head;
while( iter->link && iter->link->data < Packet )
      iter = iter->link;

Then insert a new Node to follow iter in the list.
1
2
3
4
5
 
sNode *temp=new Node;
temp->packet = Packet;
temp->data = Data;
temp->link = iter->link;
iter->link = temp;


Hope that helps!


Consider adding this constructor to your Node structure:
 
 
Node(int Packet, string Data, Node* Link): packet(Packet), data(Data), link(Link){}

It turns code like this:
1
2
3
4
5
 
sNode *temp=new Node;
temp->packet = Packet;
temp->data = Data;
temp->link = iter->link;
iter->link = temp;

Into this: iter->link = new Node( Packet, Data, iter->link);

EDIT: Nice to meet another amateur who's just learning this stuff for fun.
I've never worked in the field (though I would like to) and have no formal education in C.S. beyond a couple of college intro. courses.
Last edited on
Topic archived. No new replies allowed.