Списки

import java.util.Random;


// Листы и все, что с ними связанно

public class Main {
    private static int FICT_NUMBER = -9999;

        public static void main(String[] args) {


            System.out.println("DL Lists");
            System.out.println("List 1 an 0");
            DLNode some = CreateDL(10, 0, 1);
            printList(some);
            some = order(some);
            System.out.println("Orderind");
            printList(some);
            System.out.println("List from 10 to -10");
            some = CreateDL(50, -10, 10);
            some = makeFictList(some);
            printList(some);

            some = shift(some, 23);
            System.out.println("Shift");


            DLNode ff = createDLNode(1);
            DLNode neww = createDLNode(2);
            ff = addFirst(ff, neww);
            neww = createDLNode(2);
            ff = addFirst(ff, neww);
            neww = createDLNode(3);
            ff = addFirst(ff, neww);
            neww = createDLNode(4);
            ff = addFirst(ff, neww);
            neww = createDLNode(2);
            ff = addFirst(ff, neww);
            neww = createDLNode(5);
            ff = addFirst(ff, neww);
            neww = createDLNode(5);
            ff = addFirst(ff, neww);
            neww = createDLNode(5);
            ff = addFirst(ff, neww);
            neww = createDLNode(5);
            ff = addFirst(ff, neww);
            neww = createDLNode(2);
            ff = addFirst(ff, neww);
            neww = createDLNode(5);
            ff = addFirst(ff, neww);
            neww = createDLNode(5);
            ff = addFirst(ff, neww);
            neww = createDLNode(5);
            ff = addFirst(ff, neww);
            printList(ff);
            int nn = NumBetween(ff, 2);
            System.out.println("Num between 2 is " + nn);
//          some = deleteBetween(some, 1);
//          System.out.println("Delete between");
            //printList(some);
//          System.out.println("Delete Duplication");
            some = deleteDuplicates(some);
//          printList(some);
//          System.out.println("Sorting");
//          some = selectionSort(some);
//          printList(some);
//          System.out.println("Revers");
//          some = DelFict(some);
//          some = reverseList(some);
//          printList(some);
//          System.out.println("Delete not prime");
//          some = delNotPrime(some);
//          printList(some);
//          System.out.println("Print without negative");
//          printWithout(some);
//          System.out.println("Delete Mid");
//          some = DelMid(some);
//          printList(some);
//          SLNode newList = createSecondList(some, 6);


            System.out.println("------------------------");
            System.out.println("SLList is number");
            int num = 13;
            SLNode n = IntToList(num);
            System.out.println("Number is " + num);
            printList(n);
            int num2 = 9999;
            SLNode m = IntToList(num2);
            System.out.println("Number is " + num2);
            printList(m);

            SLNode sum = Sum(m, n);
            System.out.println("Sum is " + (num + num2));
            printList(sum);

            long res = twoBase(num);
            System.out.println("Numer " + num + " in two base: " + res);




            System.out.println("------------------------");
            int x = 99223323;
            SLNodeChar head = ChengeBase(x, 10);
            System.out.println("Number " + x + " in 16-BASE");
            printList(head);
            head = MakeCircle(head);

            head = DeleteBetween(head, '2');
            head = DelCircle(head);
            printList(head);


            System.out.println("------------------------");
            System.out.println("SL Lists");
            SLNode list = CreateSL(11, -10, 10);
            System.out.println("List from 10 to -10");
            printList(list);
            list = deltaAfter(list);
            System.out.println("Delta after");
            printList(list);

            System.out.println("Sorting");
            list = selectionSort(list);
            printList(list);

            System.out.println("Fib");
            SLNode fib = Fib(100);
            printList(fib);
//          System.out.println("Print without negative");
//          printWithout(list);
//          System.out.println("Delete Mid");
//          list = DelMid(list);
//          printList(list);

        }

//ПРОСТЕ ЧИСЛО
                public static boolean Prime(int val) {
                    if(val <= 1) return false;
                    boolean isPrime = true;
                    for(int i = 2; i <= Math.sqrt(val) && isPrime; i++) {
                        if(val % i == 0) isPrime = false;
                    }
                    return isPrime;
                }

//ДВОИЧНАЯ СИСТЕМА
                public static long twoBase(int ten) {
                    if(ten == 0) return 0;
                    int isNegative = 1;
                    if(ten < 0) {
                        isNegative = -1;
                        ten = ten *isNegative;
                    }
                       SLNode head = null;
                       while(ten != 0) {
                           SLNode node = createSLNode(ten % 2);
                           head = addFirst(head, node);
                           ten = ten / 2;
                       }
                     long res = 0;
                     while(head != null) {
                         res = res * 10 + head.data;
                         head = head.next;
                     }
                     return res * isNegative;
                }

//--------------------------------------------------------------------
//                          SLList
//--------------------------------------------------------------------

//Принт списка
                private static void printList(SLNode list) {
                    if(list == null) {
                        System.out.println("Your list is empty.");
                    }else {
                        while(list != null) {
                            System.out.printf(list.data + "   ");
                            list = list.next;
                        }
                    }
                    System.out.println("");
                }
// Принт без отрцательных
                private static void printWithout(SLNode list) {
                    if(list == null || list.data == FICT_NUMBER) {
                        System.out.println("Your list is empty.");
                    }else {
                        while(list != null && list.data != FICT_NUMBER) {
                            if(list.data >= 0)
                            System.out.printf(list.data + "   ");
                            list = list.next;
                        }
                    }
                    System.out.println("");
                }
//Создание и заполнение списка рандомными числами
                private static SLNode CreateSL(int len, int from, int to) {
                    SLNode head = null;
                    SLNode tail = null;
                    Random rand = new Random();
                    for (int i = 0; i < len; i++) {
                        SLNode node = createSLNode(rand.nextInt(to - from + 1) + from);
                        if(head == null || tail == null) {
                            head = node;
                            tail = node;
                        }
                        else {
                            tail.next = node;
                            tail = node;
                        }
                    }
                    return head;
                }
//Просто создание узла
                private static SLNode createSLNode(int data) {
                    SLNode newNode = new SLNode();
                    newNode.data = data;
                    newNode.next = null;
                    return newNode;

                }

//Из двух упорядоченных получить один упорядоченный
                public static SLNode mergeTwoLists(SLNode l1, SLNode l2) {
                    if (l1 == null) {
                        return l2;
                    }
                    else if (l2 == null) {
                        return l1;
                    }
                    else if (l1.data < l2.data) {
                        l1.next = mergeTwoLists(l1.next, l2);
                        return l1;
                    }
                    else {
                        l2.next = mergeTwoLists(l1, l2.next);
                        return l2;
                    }

                }

//Отнять от каждого элемента минимальный среди последующих
                public static SLNode deltaAfter(SLNode head) {
                    if (head == null)
                        return head;
                    SLNode node = head;
                    while(node.next != null) {
                        SLNode min = minNode(node.next);
                        node.data -= min.data;
                        node = node.next;
                    }
                    return head;
                }
//Реверс списка
                    public static SLNode reverseList(SLNode head) {
                        SLNode prev = null;
                        SLNode curr = head;
                        while (curr != null) {
                            SLNode nextTemp = curr.next;
                            curr.next = prev;
                            prev = curr;
                            curr = nextTemp;
                        }
                        return prev;
                    }

//Сортировка
                private static SLNode selectionSort(SLNode h) {
                    SLNode s = null;
                    while (h != null) {
                        SLNode max = maxNode(h);
                        h = remove(h, max);
                        max.next = null;
                        s = addFirst(s, max);
                    }
                    return s;
                }


 //Поиск максимальной и минимальной Ноды
            public static SLNode maxNode(SLNode h) {
                if (h == null)
                    return h;
                else {
                    SLNode max = h;
                    SLNode cur = h;
                    while (cur != null) {
                        if (cur.data > max.data) {
                            max = cur;
                        }
                        cur = cur.next;
                    }
                    return max;
                }
            }

            public static SLNode minNode(SLNode h) {
                if (h == null)
                    return h;
                else {
                    SLNode min = h;
                    SLNode cur = h;
                    while (cur != null) {
                        if (cur.data < min.data) {
                            min = cur;
                        }
                        cur = cur.next;
                    }
                    return min;
                }
            }

 //Удаление элемента
                    public static SLNode remove(SLNode h, SLNode x) {
                        if(h == null || x == null) return h;
                        if(h == x) {
                            return h.next;
                        }
                        SLNode pres = h;
                        while(pres != null && pres.next != x) {
                            pres = pres.next;
                        }
                        if(pres == null) return h;
                        pres.next = pres.next.next;
                        return h;
                    }

//Добавление в начало
                public static SLNode addFirst(SLNode h, SLNode newNode) {
                    if(newNode == null) {
                        return h;
                    }
                    newNode.next = h;
                    return newNode;
                }


//Поиск хвостика
                public static SLNode tailSearch(SLNode h) {
                    if (h == null)
                        return h;
                    SLNode t = h;
                    while(t.next != null) {
                        t = t.next;
                    }
                    return t;
                }
//Добавление после максимального
                private static SLNode addAfterMAX(SLNode head, SLNode node) {
                    if(head == null) {
                        return node;
                    }
                    if(node == null) {
                        return head;
                    }
                    SLNode max = maxNode(head);
                    node.next = max.next;
                    max.next = node;
                    return head;
                }
// Число -> список
                public static SLNode IntToList(int val) {
                   if(val < 0) return null;
                   SLNode head = null;
                   do {
                       SLNode node = createSLNode(val % 10);
                       head = addFirst(head, node);
                       val = val / 10;
                   }while(val != 0);
                   return head;
                }

// Список -> число
                public static int ListToInt(SLNode val) {
                    int res = 0;
                     while(val != null) {
                         res = res * 10 + val.data;
                         val = val.next;
                     }
                   return res;
                }

//Удаление центральной ноды
                public static SLNode DelMid(SLNode head) {
                    if(head ==null) return head;

                    SLNode mid = head;
                    SLNode tail = head;
                    while(tail.next != null && tail.next.next != null) {
                        mid = mid.next;
                        tail = tail.next.next;
                    }
                    if(tail.next == null) {
                        head = remove(head, mid);
                    }
                    return head;
                }

//Сума чисел
                public static SLNode Sum(SLNode l1, SLNode l2) {
                    int one = ListToInt(l1);
                    int two = ListToInt(l2);
                    SLNode res = IntToList(one + two);
                    return res;
                }


//Фибоначи в список, плиз
                public static SLNode Fib(int N) {
                    if(N < 0) return null;
                    int l = 1;
                    int h = 1;
                    SLNode res = createSLNode(l);
                    while(h <= N) {
                        h = l + h;
                        l = h - l;
                        SLNode node = createSLNode(l);
                        res = addFirst(res, node);
                    }
                    return res;
                }


//-----------------------------------------------------------------
//                  SLList CHAR
//-----------------------------------------------------------------

                private static SLNodeChar createSLNode(char data) {
                    SLNodeChar newNode = new SLNodeChar();
                    newNode.data = data;
                    newNode.next = null;
                    return newNode;

                }
                public static SLNodeChar addFirst(SLNodeChar h, SLNodeChar newNode) {
                    if(newNode == null) {
                        return h;
                    }
                    newNode.next = h;
                    return newNode;
                }

                private static void printList(SLNodeChar list) {
                    if(list == null) {
                        System.out.println("Your list is empty.");
                    }else {
                        while(list != null) {
                            System.out.printf(list.data + " ");
                            list = list.next;
                        }
                    }
                    System.out.println("");
                }
//Число в 16-ричной
               public static SLNodeChar ChengeBase(int x, int base) {
                    char [] systemElements = {'0', '1', '2', '3', '4', '5', '6', '7', '8', '9',
                            'A','B','C','D','E','F','G','H','I',
                            'J','K','L','M','N','O','P','Q',
                            'R','S','T','U','V','W','X','Y','Z'};
                    int isNegative = 1;
                    if(x < 0) isNegative = -1;
                    x = x * isNegative;
                    SLNodeChar head = null;
                    do {
                        SLNodeChar node = createSLNode(systemElements[x % base]);
                        head = addFirst(head, node);
                        x = x / base;
                    }while (x != 0);
                    if(isNegative == -1) {
                        SLNodeChar node = createSLNode('-');
                        head = addFirst(head, node);
                    }
                    return head;
                }
//Делаем кольцо
               public static SLNodeChar MakeCircle(SLNodeChar head) {
                   SLNodeChar tail = head;
                       while(tail.next != null){
                           tail = tail.next;
                   }
                       tail.next = head;

                    return head;
                }
//удаляем кольцо
               public static SLNodeChar DelCircle(SLNodeChar head) {
                   SLNodeChar tail = head;
                       while(tail.next != head){
                           tail = tail.next;
                   }
                       tail.next = null;

                    return head;
                }
//Удаляем в кольце между двумя вхождениями
               public static SLNodeChar DeleteBetween(SLNodeChar head, char X) {
                   SLNodeChar searcher = head;
                   //First
                   SLNodeChar f = null;
                   if(head.data == X) f = head;
                   else {
                       searcher = searcher.next;
                       while(searcher != head && f == null){
                           if(searcher.data == X) f = searcher;
                           searcher = searcher.next;
                       }
                   }
                 //Second
                   SLNodeChar s = null;
                   if(f != null) {
                           while(searcher != head){
                           if(searcher.data == X) {
                               s = searcher;
                           }
                           searcher = searcher.next;
                       }
                       if(s != null)
                           f.next = s;
                   }



                    return head;
                }

//-----------------------------------------------------------------
//                            DLList
//-----------------------------------------------------------------

//Принт списка
                private static void printList(DLNode list) {
                    if(list == null || list.data == FICT_NUMBER) {
                        System.out.println("Your list is empty.");
                    }else {
                        while(list != null && list.data != FICT_NUMBER) {
                            System.out.printf(list.data + "   ");
                            list = list.next;
                        }
                    }
                    System.out.println("");
                }
// Принт без отрцательных
                private static void printWithout(DLNode list) {
                    if(list == null || list.data == FICT_NUMBER) {
                        System.out.println("Your list is empty.");
                    }else {
                        while(list != null && list.data != FICT_NUMBER) {
                            if(list.data >= 0)
                            System.out.printf(list.data + "   ");
                            list = list.next;
                        }
                    }
                    System.out.println("");
                }

//Создание и заполнение списка рандомом
                private static DLNode CreateDL(int len, int from, int to) {
                    DLNode head = null;
                    DLNode tail = null;
                    Random rand = new Random();
                    for (int i = 0; i < len; i++) {
                        DLNode node = createDLNode(rand.nextInt(to - from + 1) + from);
                        if(head == null || tail == null) {
                            head = node;
                            tail = node;
                        }
                        else {
                            tail.next = node;
                            node.prev = tail;
                            tail = node;
                        }
                    }
                    return head;
                }
//Просто создание узла
                private static DLNode createDLNode(int data) {
                    DLNode newNode = new DLNode();
                    newNode.data = data;
                    newNode.next = null;
                    newNode.prev = null;
                    return newNode;

                }

//Удаление элементов между первым и последнив вхождением ЧИСЛА Х (НЕ РАБОТАЕТ)
                private static DLNode deleteBetween(DLNode head, int X) {
                    if(head == null) return head;
                    head = DelFict(head);
                    DLNode first = head;
                    DLNode last = tailSearch(head);
                    while(first != last && first.data != X){
                        first = first.next;
                    }
                    while(first != last && last.data != X) {
                        last = last.prev;
                    }
                    if(first == last) return head;
                    first.next = last;
                    last.next = first;
                    return head;

                }
//Удаление повторяющихся элементов из несортерованного списка
                public static DLNode deleteDuplicates(DLNode head) {
                    head = selectionSort(head);
                    head = DelFict(head);
                    DLNode current = head;
                    while (current != null && current.next != null) {
                        if (current.next.data == current.data) {
                            current.next = current.next.next;
                        } else {
                            current = current.next;
                        }
                    }
                    head = makeFictList(head);
                    return head;
                }

//Добавление в конец и в начало
        private static DLNode addInTheEnd(DLNode head, DLNode node) {
            if(head == null) {
                return node;
            }
            if(node == null) {
                return head;
            }
            DLNode tail = head;
            while(tail.next != null) {
                tail = tail.next;
            }
            tail.next = node;
            node.prev = tail;
            return head;
        }

        public static DLNode addFirst(DLNode h, DLNode newNode) {
            if(newNode == null) return h;

            newNode.prev = null;
            newNode.next = h;
            if (h != null) {
                h.prev = newNode;
            }
            return newNode;
        }

// 0 and 1
        private static DLNode order(DLNode head) {
            DLNode pres = head;
            DLNode zero = null;
            DLNode one = null;
            DLNode tmp = null;
            while(pres != null) {
                    //Delete
                    if (pres.next != null) {
                        pres.next.prev = pres.prev;
                    }
                    tmp = pres;
                    //Move
                    pres = pres.next;
                    tmp.next = null;
                    //Add in the end
                    if(tmp.data == 0) {
                        zero = addInTheEnd(zero, tmp);
                    }
                    else {
                        one = addInTheEnd(one, tmp);
                    }
            }
            //Connection
            zero = addInTheEnd(zero, one);
            return zero;
        }




//  Selection sort
        private static DLNode selectionSort(DLNode h) {

            DLNode s = null; // head of sorted list
            //Гениально...
            h = DelFict(h);
            while (h != null) {

                // find the node with maximum value in the unsorted list
                DLNode max = maxNode(h);
                // remove the node with maximum value from unsorted list
                h = remove(h, max);
                // insert the node with maximum value at the front of sorted list
                s = addFirst(s, max);
            }
            s = makeFictList(s);
            return s;
        }
//Создание фиктивного узла
        public static DLNode makeFictList(DLNode h) {
            DLNode fict = createDLNode(FICT_NUMBER);
            DLNode tail = tailSearch(h);
            tail.next = fict;
            fict.prev = tail;
            h.prev = fict;
            fict.next = h;
            return h;
        }
//Удаление фиктивного узла
        public static DLNode DelFict(DLNode h) {
            if(h == null) return h;
            if(h.prev == null) return h;
            h.prev.prev.next = null;
            h.prev = null;
            return h;
        }
//Поиск хвостика
        public static DLNode tailSearch(DLNode h) {
            if (h == null)
                return h;
            DLNode t = h;
            while(t.next != null) {
                t = t.next;
            }
            return t;
        }
//Поиски максимального элемента
        public static DLNode maxNode(DLNode h) {
            if (h == null || h.data == FICT_NUMBER)
                return h;
            else {
                DLNode max = h;
                DLNode cur = h;
                while (cur != null && cur.data != FICT_NUMBER) {
                    if (cur.data > max.data) {
                        max = cur;
                    }
                    cur = cur.next;
                }
                return max;
            }
        }
//Удаление элемента
        public static DLNode remove(DLNode h, DLNode x) {
            if(h == null) return h;
            // check if x is the head
            if (x.prev != null) {
                x.prev.next = x.next;
            } else {
                h = h.next;
            }
            // check if x is the tail
            if (x.next != null) {
                x.next.prev = x.prev;
            }
            return h;
        }

//Реверс
        public static DLNode reverseList(DLNode head) {
            DLNode prev = null;
            DLNode curr = head;
            while (head != null) {
                DLNode nextTemp = curr.next;
                head = remove(head, curr);
                prev = addFirst(prev, curr);
                curr = nextTemp;
            }
            return prev;
        }

// Удаление всех непростых чисел
        public static DLNode delNotPrime(DLNode head) {
            DLNode del = null;
            DLNode pres = head;
            while (pres != null) {
                if(!Prime(pres.data)) {
                    del = pres;
                    pres = pres.next;
                    head = remove(head, del);
                }
                else {
                    pres = pres.next;
                }
            }
            return head;
        }

//Удаление центральной ноды
        public static DLNode DelMid(DLNode head) {
            if(head ==null) return head;

            DLNode mid = head;
            DLNode tail = head;
            while(tail.next != null && tail.next.next != null) {
                mid = mid.next;
                tail = tail.next.next;
            }
            if(tail.next == null) {
                head = remove(head, mid);
            }
            return head;
        }

//Сдвиг списка на Н вправо
        public static DLNode shift(DLNode head, int X) {
            if(head ==null) return head;
            DLNode fict = head.prev;
            head.prev = head.prev.prev;
            head.prev.next = head;
            if(X > 0)
            for(int i = 0; i < X; i++) {
                head = head.next;
            }
            else
                for(int i = 0; i > X; i--) {
                    head = head.prev;
                }
            fict.next = head;
            fict.prev = head.prev;
            head.prev.next = fict;
            head.prev = fict;
            return head;
        }


        public static int NumBetween(DLNode head, int X) {
            int res = 0;
            int counter = 0;
            DLNode searcher = head;
               //First
                DLNode f = null;
               if(head.data == X) f = head;
               else {
                   searcher = searcher.next;
                   while(searcher != null && f == null){
                       if(searcher.data == X) f = searcher;
                       searcher = searcher.next;
                   }
               }

               if(f != null) {
                       while(searcher != null){
                       if(searcher.data == X) {
                           res += counter;
                           counter = 0;
                       }
                       counter++;
                       searcher = searcher.next;
                   }
               }
               return res;

        }
//Удаление из двонаправленного и вставка в однонаправленный (меньшиз, чем икс)
//НУЖНО СДЕЛАТЬ ГЛОБАЛЬНУЮ ПЕРЕМЕННУЮ, ЧТОБ ОНО РАБОТАЛО
//ИЛИ ВКЛЮЧИТЬ ВИЗУАЛИЗАЦИЮ
        private static SLNode createSecondList(DLNode dlHead, int x) {
//Визуализация
            System.out.println("Delete all nodes less then " + x);
            System.out.println("Before");
            printList(dlHead);
//Конец Визуализации

            SLNode newNode = null;
            SLNode slHead = null;
            DLNode present = dlHead;
            while(present != null) {
                if(present.data < x) {
                    newNode = createSLNode(present.data);
                    slHead = addFirst(slHead, newNode);
                    dlHead = remove(dlHead, present);
                }
                present = present.next;
            }

//Визуализация
            System.out.println("After");
            printList(dlHead);
            System.out.println("New List");
            printList(slHead);
//Конец Визуализации

            return slHead;
        }


    }