Double Linked List, Swaping Nodes

[salem c]

Edit:
Another shitty "post, delete and run away" drive-by pissed on the forum and made a meaningless set of replies.


> //Swap base temps
> nodeA_n = nodeB_n;
> nodeA_p = nodeB_p;
Are you really swapping the nodes, or just the local variable copies?

> if(tail == nodeB)
> tail == nodeA;
If your compiler isn't warning you about useless comparisons (you meant assignment right?), then increase the warning level.

Draw yourself a picture (or 10).

                     it1                              it2
        +-----+    +-----+    +-----+    +-----+    +-----+    +-----+    
head--->|     |--->|     |--->|     |--->|     |--->|     |--->|     |--->NULL
        |  A  |    |  B  |    |  C  |    |  D  |    |  E  |    |  F  |    
NULL<---|     |<---|     |<---|     |<---|     |<---|     |<---|     |<---tail
        +-----+    +-----+    +-----+    +-----+    +-----+    +-----+    


                     it1                              it2
        +-----+    +-----+    +-----+    +-----+    +-----+    +-----+    
head--->|     |--->|     |--->|     |--->|     |--->|     |--->|     |--->NULL
        |  A  |    |  E  |    |  C  |    |  D  |    |  B  |    |  F  |    
NULL<---|     |<---|     |<---|     |<---|     |<---|     |<---|     |<---tail
        +-----+    +-----+    +-----+    +-----+    +-----+    +-----+    

Two swap a pair of nodes in a DLL, there are 8 assignments you need to make.
- two for each of the nodes that move.
- one each for the next or prev of it's new neighbours

As you write one line of code to perform one of these assignments, tick it off on the diagram.

[JLBorges]

Writing some code as debugging scaffold would help.
Use it to dump intermediate values to see what is going on.

Here is some starter code:

#include <iostream>
#include <iterator>

template < typename T > struct list
{
    using value_type = T ;
    private: struct iterator ; public:

    iterator begin() { return { first, last } ; }
    iterator end() { return { nullptr, last } ; }

    bool empty() const noexcept { return first == nullptr ; }

    void push_back( const T& v )
    {
        if( empty() ) first = last = new node { v, nullptr, nullptr } ;
        else
        {
            last->next = new node { v, nullptr, last } ;
            last = last->next ;
        }
    }

    void print() // note: not const since we haven't (yet) implemented const_iterators
    {
        for( const auto& v : *this ) std::cout << v << " => " ;
        std::cout << " nullptr\n" ;
    }

    void debug_dump() const
    {
        std::cout << "nodes:\n" ;
        for( const node* n = first ; n != nullptr ; n = n->next ) dump_node(n) ;
        std::cout << "\n----------------------\n" ;
    }

    iterator find( const T& v ) // note: not const since we haven't (yet) implemented const_iterators
    {
        for( auto iter = begin() ; iter != end() ; ++iter ) if( iter.current->value == v ) return iter ;
        return end() ; // not found
    }

    void swap_nodes( iterator a, iterator b ) { do_swap_nodes( a.current, b.current ) ; }

    private:

        struct node
        {
            T value ;
            node* next ;
            node* prev ;
        };

        node* first = nullptr ;
        node* last = nullptr ;

        struct iterator
        {
            using value_type = T ;
            using iterator_category = std::bidirectional_iterator_tag ;
            using reference = T& ;
            using pointer = T* ;
            using difference_type = std::ptrdiff_t ;

            reference operator*() { return current->value ; }
            pointer operator&() { return std::addressof( **this ) ; }

            iterator& operator++ () { current = current->next ; return *this ; }
            iterator operator++ (int) { const auto oldv = *this ; ++*this ; return oldv ; }

            iterator& operator-- () { current = current ? current->prev : last ; return *this ; }
            iterator operator-- (int) { const auto oldv = *this ; --*this ; return oldv ; }

            bool operator== ( const iterator& that ) const noexcept { return current == that.current ; }
            bool operator!= ( const iterator& that ) const noexcept { return !( *this == that ) ; }

            node* current ;
            node* last ;
        };

        static void dump_node( const node* n )
        {
            std::cout << "node at address: " << n << "  value: " << n->value
                      << "  next: " << n->next << "  prev: " << n->prev << '\n' ;
        }

        void do_swap_nodes( [[maybe_unused]] node* a, [[maybe_unused]] node* b ) // unused as of now
        {
            // TO DO: implement, test, debug this function
            // use debug_dump() to aid in the debugging
        }
};

int main()
{
    list<int> lst ;
    for( int v = 0 ; v < 10 ; ++v )
    {
        lst.push_back(v) ;
        // lst.print() ;
        // lst.debug_dump() ;
    }

    lst.print() ;
    lst.debug_dump() ;

    // uncomment after implementing swap_nodes
    /*
    const auto iter_three = lst.find(3) ;
    const auto iter_seven = lst.find(7) ;
    lst.swap_nodes( iter_three, iter_seven ) ;
    std::cout << "after swap\n" ;
    lst.print() ;
    lst.debug_dump() ;
    */
}

http://coliru.stacked-crooked.com/a/71bab4efb1cf4053