Linked List

This is a discussion on Linked List within the C++ Programming forums, part of the General Programming Boards category; I have made a linked list with the following functions. Code: class node { public: int data; node* next; }; ...

  1. #1
    Registered User
    Join Date
    Mar 2009
    Posts
    112

    Linked List

    I have made a linked list with the following functions.
    Code:
    class node
    {
    public:
    	int data;			node* next;
    };
    
    class linkedList: public node
    {
    	node* head;
    public:
    linkedList()
    void insertEnd( int data)                       // Inserts the node at end 
    void insertStart(int data)                      // Inserts the node at start
    void search(int l)                                  // Searches the data in nodes 
    void deleteAnode(int l)                        // Delete any node (expect first or last) 
    void deleteSNode()                             //  Delete start node  
    void deleteENode()                             //  Delete end node
    Now i want to make a function like which inserts a node in between two nodes.
    So I have to take the nodes data , between which i want to add a new node?

    Would it be like this ?
    Code:
    void insertAnywhere( int previous, int next, int new)
    {
    
    }
    Or is there a better way kindly tell.

  2. #2
    Jack of many languages Dino's Avatar
    Join Date
    Nov 2007
    Location
    Katy, Texas
    Posts
    2,309
    Since you have a singly-linked, forward-only linked list, and you want to insert a new node (C) between two existing nodes (A and B), it will be a waste of time to pass the second link (B) in the parm list.

    Check A.next for NULL. If NULL, set A.next to C and you are done.

    However, if A.next is not NULL, then set C.next to the value in A.next, then you can set A.next to C.

    EDIT: Actually, that's too much checking, and I assume you are using NULL for a placeholder. This can be done blindly with the following logic:
    1) set C.next to the value from A.next
    2) set A.next to C.
    Last edited by Dino; 02-19-2010 at 06:56 AM.
    Mac and Windows cross platform programmer. Ruby lover.

    Quote of the Day
    12/20: Mario F.:I never was, am not, and never will be, one to shut up in the face of something I think is fundamentally wrong.

    Amen brother!

  3. #3
    Registered User
    Join Date
    Mar 2009
    Posts
    112
    Code:
    void Sort()
    	{
    	node* first;
    	node* second;
    	node* temp;
    	
    	first=head;
    		
    		while(first->next!=NULL)
    		{
    			second=first->next;
    			while(second->next!=NULL)
    			{
    		
    				if(first->data < second->data)
    				{
    					temp = new node;
    					temp->data=first->data;
    					first->data=second->data;
    					second->data=temp->data;
    					delete temp;
    				}
    			second=second->next;
    			}
    			
    		first=first->next;
    		}
    	}
    This is the sorting function for the singly linked list , but it does not sort the list . Plus i want to know if there is another better way?

  4. #4
    Jack of many languages Dino's Avatar
    Join Date
    Nov 2007
    Location
    Katy, Texas
    Posts
    2,309
    A better way is to rearrange the list, rather than allocate new and delete throughout the loop.
    Mac and Windows cross platform programmer. Ruby lover.

    Quote of the Day
    12/20: Mario F.:I never was, am not, and never will be, one to shut up in the face of something I think is fundamentally wrong.

    Amen brother!

  5. #5
    Registered User
    Join Date
    Mar 2009
    Posts
    112
    how ??

  6. #6
    Jack of many languages Dino's Avatar
    Join Date
    Nov 2007
    Location
    Katy, Texas
    Posts
    2,309
    By swapping pointers using temp, but temp is statically allocated in your sort function. You'll need to carry three pointers: previous, current and next.
    Mac and Windows cross platform programmer. Ruby lover.

    Quote of the Day
    12/20: Mario F.:I never was, am not, and never will be, one to shut up in the face of something I think is fundamentally wrong.

    Amen brother!

  7. #7
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,304
    Use Insertion Sort:

    Use two lists. Take an item out of your unsorted list, and "insert" it into your new sorted list, by moving along the list to the right position before inserting it.
    Repeat until your first list is empty, then your second list contains the sorted data.
    Now swap the second list with your original one (actually just copy the head pointer across) and you're done.

    This is the simplest method of sorting a singly-linked-list.
    My homepage
    Advice: Take only as directed - If symptoms persist, please see your debugger

    Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. C++ Linked list program need help !!!
    By dcoll025 in forum C++ Programming
    Replies: 1
    Last Post: 04-20-2009, 10:03 AM
  2. Following CTools
    By EstateMatt in forum C Programming
    Replies: 5
    Last Post: 06-26-2008, 10:10 AM
  3. Reverse function for linked list
    By Brigs76 in forum C++ Programming
    Replies: 1
    Last Post: 10-25-2006, 10:01 AM
  4. Template Class for Linked List
    By pecymanski in forum C++ Programming
    Replies: 2
    Last Post: 12-04-2001, 08:07 PM
  5. singly linked list
    By clarinetster in forum C Programming
    Replies: 2
    Last Post: 08-26-2001, 10:21 PM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21