Split doubly linked list

[nowy20180820]

I have got a doubly linked list
and pointer to the node
How can I write splitAfter and splitBefore functions
Functions have to include border cases

These functions would be helpful when i
play with divide and conquer algorithms on linked list

For example splitting node for recursive merge sort can be found in this way

p = L.head;
q = L.tail;
while (p != q && p->next != q )
{
     p = p->next;
     q = q->prev;
}
return p;

Here we need splitAfter function

p = L.head;
q = L.head;
while(q != NULL && q->next != NULL)
{
      p = p->next;
      q = q->next->next;
}
return p;

Here we need splitBefore function

[JLBorges]

The standard library has a doubly linked list https://en.cppreference.com/w/cpp/container/list
It supports splicing; https://en.cppreference.com/w/cpp/container/list/splice
split can be implemented in terms of splice.

For example:

#include <iostream>
#include <list>
#include <string>
#include <algorithm>

template < typename T, typename A >
std::list<T,A> split_before( std::list<T,A>& lst, typename std::list<T,A>::const_iterator here )
{
    std::list<T,A> second_list ;

    // https://en.cppreference.com/w/cpp/container/list/splice
    second_list.splice( second_list.begin(), lst, here, lst.end() ) ;

    return second_list ;
}

template < typename T, typename A >
std::list<T,A> split_after( std::list<T,A>& lst, typename std::list<T,A>::const_iterator here )
{
    if( here == lst.end() ) return {} ; // return empty list
    else return split_before( lst, ++here ) ;
}

template < typename SEQ > void print( const SEQ& seq )
{
    std::cout << "[ " ;
    for( const auto& v : seq ) std::cout << v << ' ' ;
    std::cout << "]\n" ;
}

int main()
{
    std::list<std::string> a = { "Church", "Turing", "Ada", "Knuth", "Wirth", "Dijkstra",
                                 "Neumann", "Kleene", "Minsky", "Ritchie", "Thomson", "Stroustrup" } ;
    print(a) ;

    std::cout << "\nsplit after Dijkstra:\n" ;
    auto b = split_after( a, std::find( a.begin(), a.end(), "Dijkstra" ) ) ;
    print(a) ;
    print(b) ;

    std::cout << "\nsplit second list before Ritchie:\n" ;
    const auto c = split_before( b, std::find( b.begin(), b.end(), "Ritchie" ) ) ;
    print(a) ;
    print(b) ;
    print(c) ;
}

http://coliru.stacked-crooked.com/a/a6253ec87cee617b

[nowy20180820]

Yes but ready solutions from STL dont show how it works
I will need these functions to play with divide and conquer functions

Hindu guy from youtube wrote find_middle function and merge function
His middle node is in fact head of second linked list so we need splitBefore
If we write our own find middle function we will need splitAfter function

[jonnin]

pointer manipulations.
to split before a node,
head2 = node; //new list starts here. //this may be several assignment statements, eg next/prev
oldlistcurrent -> next = null; //chop off before node in original list. assuming ->next is node in question.

to split after a node: call the above on node->next ;)

that is, I am assuming if list is 1,2,3,4,5 and node is 3:
split before is
list 1: 1,2
list 2: 3,4,5
and split after is
list 1: 1,2,3
list 2: 4,5

be sure to check nulls and set nulls and such. new list -> prev is null @ new head. old list tail -> next is null. right?

[dhayden]

Definitely implement split_after() by using split_before().

If you can't keep the points straight in your head, draw them out on a piece of paper. Use one color pen to draw the pointers before the split and a different code to draw the pointers after the split.

[nowy20180820]

Dave your Concat function was really helpful for partition sort
Idea for partition i saw in Gonnet & Baeza handbook but in the internet
there is Goodrich and Tamassia slides with the same concept for partition

Can i use split_before() to implement split_after()
What about base cases are they the same ?


split_before() and split_after() are as useful for merge_sort() as Concat()
for partition_sort()

[jonnin]

you can use either before or after, write one and you can use it to make the other one.

all you have to check is that the input pointer is not null, so you can dereference it to pass that to the other one.
eg, if you did before first, then after is splitbefore(input->next) so input better not be null. If it is, just return null. similar if you do after first.

Note that the one you wrote first will have additional pointer / edge case checks.

[nowy20180820]

#include<iostream>
#include<cstdlib>
#include<ctime>

struct Node
{
    int key;
    struct Node *prev;
    struct Node *next;
};

struct List
{
    struct Node *head;
    struct Node *tail;
};

void ListInit(struct List &L)
{
    L.head = nullptr;
    L.tail = nullptr;
}

bool ListIsEmpty(struct List L)
{
    return (L.head == nullptr && L.tail == nullptr);
}

Node *ListSearch(struct List L,int k)
{
    Node *x = L.head;
    while(x != nullptr && x->key != k)
        x = x->next;
    return x;
}

void ListInsert(struct List &L,int k)
{
    Node *x = new Node;
    x->key = k;
    x->next = L.head;
    if(L.head != nullptr)
        L.head->prev = x;
    L.head = x;
    x->prev = nullptr;
    if(x->next == nullptr)
        L.tail = x;
}

void ListDelete(struct List &L,int k)
{
    Node *x = ListSearch(L,k);
    if(x != nullptr)
    {
        if(x->next == nullptr)
            L.tail = x->prev;
        if(x->prev != nullptr)
            x->prev->next = x->next;
        else
            L.head = x->next;
        if(x->next != nullptr)
            x->next->prev = x->prev;
        delete x;
    }
}

void ListDispayForward(struct List L)
{
    int counter = 0;
    struct Node *p = L.head;
    while(p != nullptr)
    {
        std::cout<<p->key<<" -> ";
        p = p->next;
        counter++;
    }
    std::cout<<"NULL \n";
    std::cout<<"Liczba wezlow listy : "<< counter <<'\n';
}

void ListDispayBackward(struct List L)
{
    int counter = 0;
    struct Node *p = L.tail;
    while(p != nullptr)
    {
        std::cout<<p->key<<" -> ";
        p = p->prev;
        counter++;
    }
    std::cout<<"NULL \n";
    std::cout<<"Liczba wezlow listy : "<< counter <<'\n';
}



void ListSplitAfter(struct Node *x,struct List &L,struct List &L1,struct List &L2)
{
    struct Node *nextX;
    if(x == nullptr || x->next == nullptr)
    {
        L1.head = L.head;
        L1.tail = L.tail;
        L2.head = nullptr;
        L2.tail = nullptr;
    }
    else
    {
        nextX = x->next;
        x->next = nullptr;
        nextX->prev = nullptr;
        L1.head = L.head;
        L1.tail = x;
        L2.head = nextX;
        L2.tail = L.tail;
    }
    ListInit(L);
}


void ListSplitBefore(struct Node *x,struct List &L,struct List &L1,struct List &L2)
{
    struct Node *prevX;
    if(x == nullptr || x->prev == nullptr)
    {
        L1.head = nullptr;
        L1.tail = nullptr;
        L2.head = L.head;
        L2.tail = L.tail;
    }
    else
    {
        prevX = x->prev;
        x->prev = nullptr;
        prevX->next = nullptr;
        L1.head = L.head;
        L1.tail = prevX;
        L2.head = x;
        L2.tail = L.tail;
    }
    ListInit(L);
}

int main()
{
    int k,n,m,p;
    List L,L1,L2;
    Node *x;
    ListInit(L);
    ListInit(L1);
    ListInit(L2);
    srand(time(nullptr));
        std::cout<<"Ile liczb wylosowac \n";
        std::cin>>n;
        std::cout<<"Podaj gorny zakres przedzialu dla losowanych liczb \n";
        std::cin>>m;
        for(k = 1;k <= n;k++)
            ListInsert(L,rand()%m);
        std::cout<<"Lista L \n";
        ListDispayForward(L);
        ListDispayBackward(L);
        std::cout<<"Podaj element za ktorym chcesz rozdzielic liste \n";
        std::cin>>p;
        x = ListSearch(L,p);
        ListSplitBefore(x,L,L1,L2);
        std::cout<<"Lista L1 \n";
        ListDispayForward(L1);
        ListDispayBackward(L1);
        std::cout<<"Lista L2 \n";
        ListDispayForward(L2);
        ListDispayBackward(L2);
        std::cout<<"Lista L \n";
        ListDispayForward(L);
        ListDispayBackward(L);
        while(!ListIsEmpty(L1))
           ListDelete(L1,L1.head->key);
        while(!ListIsEmpty(L2))
           ListDelete(L2,L2.head->key);
        std::cout<<"Lista L1 \n";
        ListDispayForward(L1);
        ListDispayBackward(L1);
        std::cout<<"Lista L2 \n";
        ListDispayForward(L2);
        ListDispayBackward(L2);
       std::cout<<"Lista L \n";
        ListDispayForward(L);
        ListDispayBackward(L);
        system("PAUSE");
    return 0;
}

Can you simplify or correct this code ?

[dhayden]

Give List.head and List.tail initial values.

The ListXYZ() functions should all be methods of struct List where the parameter L becomes the "this" pointer.

Empty() doesn't need to check both head and tail. If one is null then the other should be also.

Use for loops when the loop has initialize, test, increment semantics, such as in ListSearch()

In ListInsert, rather than checking for x->next == nullptr, just put an else in the if(L.head) part

if (ptr != nullptr) is exactly equivalent to if (ptr)

Implement ListSplitBefore using ListSplitAfter
Use the assignment operator and ListInit in the Split routine.

Putting it all together:

#include<iostream>
#include<cstdlib>
#include<ctime>

struct Node
{
    int key;
    struct Node *prev;
    struct Node *next;
};

struct List
{
    struct Node *head = nullptr;
    struct Node *tail = nullptr;
    void Init();
    bool IsEmpty() { return head == nullptr; }
    Node *Search(int k);
    void Insert(int k);		// insert at head.
    void Delete(int k);
    void DisplayForward();
    void DisplayBackward();
    void SplitAfter(Node *where, List &L1, List &L2);
    void SplitBefore(Node *where, List &L1, List &L2);
};
    
void List :: Init()
{
    head = tail = nullptr;
}


Node *
List::Search(int k)
{
    for (Node *x = head; x; x = x->next) {
	if (x->key == k) return x;
    }
    return nullptr;
}

// insert at head
void
List::Insert(int k)
{
    Node *x = new Node;
    x->key = k;
    x->next = head;
    if (head) {
	head->prev = x;
    } else {
	tail = x;
    }
    head = x;
    x->prev = nullptr;
}

void
List::Delete(int k)
{
    Node *x = Search(k);
    if (x) {
	if (x->next == nullptr)
	    tail = x->prev;
	else
	    x->next->prev = x->prev;
	if (x->prev)
	    x->prev->next = x->next;
	else
	    head = x->next;
	delete x;
    }
}

void
List::DisplayForward()
{
    int counter = 0;
    for (struct Node *p = head; p; p = p->next) {
	std::cout << p->key << " -> ";
	counter++;
    }
    std::cout << "NULL \n";
    std::cout << "Liczba wezlow listy : " << counter << '\n';
}

void
List::DisplayBackward()
{
    int counter = 0;
    for (struct Node *p = tail; p; p = p->prev) {
	std::cout << p->key << " -> ";
	counter++;
    }
    std::cout << "NULL \n";
    std::cout << "Liczba wezlow listy : " << counter << '\n';
}

// Split after x. If x==nullptr, L1 gets the entire list
void
List::SplitAfter(struct Node *x, struct List &L1, struct List &L2)
{
    struct Node *nextX;
    if (x == nullptr || x->next == nullptr) {
	L1 = *this;
	L2.Init();
    } else {
	nextX = x->next;
	x->next = nullptr;
	nextX->prev = nullptr;
	L1.head = head;
	L1.tail = x;
	L2.head = nextX;
	L2.tail = tail;
    }
    Init();
}

// Split before x. If x == nullptr, L2 gets the entire list
void
List::SplitBefore(struct Node *x, struct List &L1, struct List &L2)
{
    if (x == nullptr) {
	L1.Init();
	L2 = *this;
	Init();
    } else {
	SplitAfter(x->next, L1, L2);
    }
}

int
main()
{
    int k, n, m, p;
    List L, L1, L2;
    Node *x;
    srand(time(nullptr));
    std::cout << "Ile liczb wylosowac \n";
    std::cin >> n;
    std::cout << "Podaj gorny zakres przedzialu dla losowanych liczb \n";
    std::cin >> m;
    for (k = 1; k <= n; k++)
	L.Insert(rand() % m);
    std::cout << "Lista L \n";
    L.DisplayForward();
    L.DisplayBackward();
    std::cout << "Podaj element za ktorym chcesz rozdzielic liste \n";
    std::cin >> p;
    x = L.Search(p);
    L.SplitBefore(x, L1, L2);
    std::cout << "Lista L1 \n";
    L1.DisplayForward();
    L1.DisplayBackward();
    std::cout << "Lista L2 \n";
    L2.DisplayForward();
    L2.DisplayBackward();
    std::cout << "Lista L \n";
    L.DisplayForward();
    L.DisplayBackward();
    while (!L1.IsEmpty())
	L1.Delete(L1.head->key);
    while (!L2.IsEmpty())
	L2.Delete(L2.head->key);
    std::cout << "Lista L1 \n";
    L1.DisplayForward();
    L1.DisplayBackward();
    std::cout << "Lista L2 \n";
    L2.DisplayForward();
    L2.DisplayBackward();
    std::cout << "Lista L \n";
    L.DisplayForward();
    L.DisplayBackward();
    system("PAUSE");
    return 0;
}