locked
Value Swapping in Linked List RRS feed

  • Question

  • Hi, I'm just wondering how I would swap two values in a linked list?
    I know I would first need to delete both values from their respective locations and then insert it into the list again.
    However, I don't know how I could insert into a list.

    Any code or pseudo code would be greatly appreciated.
    Monday, November 24, 2008 5:46 AM

Answers

  • You don't have to delete anything.
    There are several type of linked list. But since you don't give a lot of info about YOUR linked list, let imaging that your question is about a double one.
    So, each "cell" in a double linked list provide at least 3 fields : the address of the previous cell, the address of the following cell and the value itself.
    I propose for example this following structure to represent the cells:
    struct _Cell
    {
        _Cell* pNext;
        _Cell* pPrevious;
        int value;
    }
    So if you have a linked list like this : C1->C2->C3->C4->C5.
    You will have these statements:
    C1.pNext = &C2;
    C2.pNext = &C3;
    C3.pNext = &C4;
    C4.pNext = &C5
    C5.pNext = NULL;
    And of course:
    C1.pPrevious = NULL;
    C2.pPrevious = &C1;
    C3.pPrevious = &C2;
    C4.pPrevious = &C3;
    C5.pPrevious = &C4;
    Let code a general function Swap to swap 2 cells whatever their position. So if you want to swap C2 and C4, you'll code,
    Swap(&C2,&C4);
    Here the function:
    void Swap(Cell* p1,Cell* p2)
    {
    p1->pPrevious->pNext = p2;
    p1->pNext->pPrevious = p2;
    p2->pPrevious->pNext = p1;
    p2->pNext->pPrevious = p1;

    Cell* tmp = p1->pNext;
    p1->pNext = p2->pNext;
    p2->pNext = tmp;
    tmp = p1->pPrevious;
    p1->pPrevious = p2->pPrevious;
    p2->pPrevious = tmp;
    }

    Now, you said pseudo-code, then I proposed an algo in C.
    But I think that there are enough resource in .Net Framework Classes to find something to use in an easier way.
    Could you give more info about what you are working on ?
    • Proposed as answer by Hourlier Laurent Monday, November 24, 2008 6:27 AM
    • Marked as answer by Harry Zhu Thursday, November 27, 2008 1:24 AM
    Monday, November 24, 2008 6:26 AM
  • There is an easier way to swap values in a linked list. Given this:
    1 class MyLinkList {  
    2     MyLinkList prev;  
    3     MyLinkList next;  
    4     Object someValue;  
    5

    To swap two items in the list (listItem1, listItem2) you can do:

    1 Object temp = listItem1.someValue;  
    2 listItem1.someValue = listItem2.someValue;  
    3 listItem2.someValue = temp; 

    Messing with the prev/next references is just overkill :)

    Ron Whittle - If the post is helpful or answers your question, please mark it as such.
    • Proposed as answer by Ron.Whittle Monday, November 24, 2008 6:44 AM
    • Marked as answer by Harry Zhu Thursday, November 27, 2008 1:24 AM
    Monday, November 24, 2008 6:43 AM
  • Here's an example using the .Net Linked list class. Just swap the node values; as others have already pointed out, there's no need to remove and add elements:

    using System; 
    using System.IO; 
    using System.Diagnostics; 
    using System.Collections; 
    using System.Collections.Generic; 
     
    namespace Demo 
        public class Program 
        { 
            public static void Main() 
            { 
                LinkedList<string> list = new LinkedList<string>(); 
                 
                list.AddLast("First"); 
                list.AddLast("Second"); 
                list.AddLast("Third"); 
                list.AddLast("Fourth"); 
     
                PrintCollection(list); 
                Console.WriteLine(); 
     
                LinkedListNode<string> node = list.First; 
                node = node.Next; 
                LinkedListNode<string> secondNode = node
                node = node.Next; 
                LinkedListNode<string> thirdNode = node
     
                string temp = secondNode.Value; 
                secondNode.Value = thirdNode.Value; 
                thirdNode.Value = temp
     
                PrintCollection(list); 
            } 
     
            public static void PrintCollection(IEnumerable collection) 
            { 
                foreach (object thing in collection) 
                { 
                    Console.WriteLine(thing); 
                } 
            } 
        } 
     

    • Proposed as answer by Matthew Watson Monday, November 24, 2008 10:25 AM
    • Marked as answer by Harry Zhu Thursday, November 27, 2008 1:24 AM
    Monday, November 24, 2008 10:25 AM

All replies

  • You don't have to delete anything.
    There are several type of linked list. But since you don't give a lot of info about YOUR linked list, let imaging that your question is about a double one.
    So, each "cell" in a double linked list provide at least 3 fields : the address of the previous cell, the address of the following cell and the value itself.
    I propose for example this following structure to represent the cells:
    struct _Cell
    {
        _Cell* pNext;
        _Cell* pPrevious;
        int value;
    }
    So if you have a linked list like this : C1->C2->C3->C4->C5.
    You will have these statements:
    C1.pNext = &C2;
    C2.pNext = &C3;
    C3.pNext = &C4;
    C4.pNext = &C5
    C5.pNext = NULL;
    And of course:
    C1.pPrevious = NULL;
    C2.pPrevious = &C1;
    C3.pPrevious = &C2;
    C4.pPrevious = &C3;
    C5.pPrevious = &C4;
    Let code a general function Swap to swap 2 cells whatever their position. So if you want to swap C2 and C4, you'll code,
    Swap(&C2,&C4);
    Here the function:
    void Swap(Cell* p1,Cell* p2)
    {
    p1->pPrevious->pNext = p2;
    p1->pNext->pPrevious = p2;
    p2->pPrevious->pNext = p1;
    p2->pNext->pPrevious = p1;

    Cell* tmp = p1->pNext;
    p1->pNext = p2->pNext;
    p2->pNext = tmp;
    tmp = p1->pPrevious;
    p1->pPrevious = p2->pPrevious;
    p2->pPrevious = tmp;
    }

    Now, you said pseudo-code, then I proposed an algo in C.
    But I think that there are enough resource in .Net Framework Classes to find something to use in an easier way.
    Could you give more info about what you are working on ?
    • Proposed as answer by Hourlier Laurent Monday, November 24, 2008 6:27 AM
    • Marked as answer by Harry Zhu Thursday, November 27, 2008 1:24 AM
    Monday, November 24, 2008 6:26 AM
  • There is an easier way to swap values in a linked list. Given this:
    1 class MyLinkList {  
    2     MyLinkList prev;  
    3     MyLinkList next;  
    4     Object someValue;  
    5

    To swap two items in the list (listItem1, listItem2) you can do:

    1 Object temp = listItem1.someValue;  
    2 listItem1.someValue = listItem2.someValue;  
    3 listItem2.someValue = temp; 

    Messing with the prev/next references is just overkill :)

    Ron Whittle - If the post is helpful or answers your question, please mark it as such.
    • Proposed as answer by Ron.Whittle Monday, November 24, 2008 6:44 AM
    • Marked as answer by Harry Zhu Thursday, November 27, 2008 1:24 AM
    Monday, November 24, 2008 6:43 AM
  • Here's an example using the .Net Linked list class. Just swap the node values; as others have already pointed out, there's no need to remove and add elements:

    using System; 
    using System.IO; 
    using System.Diagnostics; 
    using System.Collections; 
    using System.Collections.Generic; 
     
    namespace Demo 
        public class Program 
        { 
            public static void Main() 
            { 
                LinkedList<string> list = new LinkedList<string>(); 
                 
                list.AddLast("First"); 
                list.AddLast("Second"); 
                list.AddLast("Third"); 
                list.AddLast("Fourth"); 
     
                PrintCollection(list); 
                Console.WriteLine(); 
     
                LinkedListNode<string> node = list.First; 
                node = node.Next; 
                LinkedListNode<string> secondNode = node
                node = node.Next; 
                LinkedListNode<string> thirdNode = node
     
                string temp = secondNode.Value; 
                secondNode.Value = thirdNode.Value; 
                thirdNode.Value = temp
     
                PrintCollection(list); 
            } 
     
            public static void PrintCollection(IEnumerable collection) 
            { 
                foreach (object thing in collection) 
                { 
                    Console.WriteLine(thing); 
                } 
            } 
        } 
     

    • Proposed as answer by Matthew Watson Monday, November 24, 2008 10:25 AM
    • Marked as answer by Harry Zhu Thursday, November 27, 2008 1:24 AM
    Monday, November 24, 2008 10:25 AM