Заказанный список ссылок:
Сортировать по ключевым значениям. При удалении заголовка цепи удаляется минимальное (/максимальное) значение. При вставке ищите позицию вставки.
При вставке вам необходимо сравнить O (n), среднее O (N/2) и при удалении минимальных (/максимальных) данных на головке цепи, эффективность o (1),
Если приложение требуется частый доступ (вставьте/находить/удалить) к наименьшим (/максимум) элементам данных, то упорядоченные связанные списки являются хорошим выбором. Приоритетные очереди могут использовать упорядоченные связанные списки для реализации вставки сортировки упорядоченных связанных списков:
Для неупорядоченного массива сортируйте его с помощью упорядоченного связанного списка, а уровень сравнения - O (n^2)
Уровень времени копии o (2*n). Поскольку количество копий невелико, данные в связанном списке перемещаются в первый раз, а затем копируются из связанного списка в массив. В раз, когда каждый раз, когда вставлена новая ссылка, нет необходимости копировать движущиеся данные, только одна или две ссылки должны изменить домен ссылки.
импортировать java.util.arrays; импортировать java.util.random; / *** Вставить массивы, сортирующие сортирование в упорядоченный список связанного списка* @author Stone*/ public Class LinkedListInsertSort <t Extends сопоставимо <T >> {Private Link <T> First; // первый узел public LinkedListInsertSort () {} public boolean isempty () {return First == null; } public void sortList (t [] ary) {if (ary == null) {return; } // Вставьте элементы массива в связанный список и сортируйте их в упорядоченном связанном списке для (t Data: ary) {insert (data); } //} public void insert (t data) {// Вставка в заголовок цепи, сортируйте от малой к большой ссылке <t> newlink = new Link <T> (data); Link <T> ток = первое, предыдущий = null; while (current! = null && data.compareto (current.data)> 0) {предыдущий = current; current = current.next; } if (предыдущий == null) {first = newlink; } else {предыдущий.next = newlink; } newlink.next = current; } public Link <T> deleteFirst () {// Удалить ссылку заголовка цепи <T> temp = First; First = First.Next; // Измените первый узел, чтобы вернуть температуру; } public Link <t> find (t t) {link <t> find = first; while (find! = null) {if (! find.data.equals (t)) {find = find.next; } else {break; }} return find; } public Link <T> delete (t t) {if (isempty ()) {return null; } else {if (first.data.equals (t)) {link <t> temp = first; First = First.Next; // изменить первый узел на следующий узел возврата; }} Link <t> p = First; Ссылка <T> Q = первое; while (! p.data.equals (t)) {if (p.next == null) {// Укажите, что возврат нуль не был найден в конце цепи; } else {q = p; p = p.next; }} Q.next = p.next; возврат P; } public void displaylist () {// Travel System.out.println ("list (first-> last):"); Ссылка <T> current = First; while (current! = null) {current.displaylink (); current = current.next; }} public void displayListerSe () {// обратная связь пересечения <T> p = первое, q = first.next, t; while (q! = null) {// Указатель изменен, порядок прохождения данных обратно t = q.next; // no3 if (p == Сначала) {// Когда это исходный заголовок, .next заголовка должен быть пустым p.next = null; } Q.next = p; // no3 -> no1 pointer обратный p = q; // старт - это обратный Q = t; // NO3 Start} // В IF в цикле выше, First.Next пуст, и когда Q является нулевым и не выполняет цикл, P является исходным наибольшим элементом данных. После инвертирования P назначается First = P; DisplayList (); } class link <t> {// точка ссылки t data; // Ссылка поля данных <T> Далее; // Последующий указатель, цепочка узла Link (t Data) {this.data = data; } void displayLink () {System.out.println ("Данные" + data.tostring ()); }} public static void main (string [] args) {linkedListInsertSort <integer> list = new LinkedListInsertSort <integer> (); Случайный случайный = new Random (); int len = 5; Integer [] ary = new Integer [len]; for (int i = 0; i <len; i ++) {ary [i] = random.nextint (1000); } System.out.println ("--------------"); System.out.println (Arrays.tostring (ary)); System.out.println ("---------------------------------------------------------------); List.sortList (ary); list.displaylist ();}}
Печать
--- Перед сортировкой ---- [595, 725, 310, 702, 444] --- После сортировки связанного списка ---- Список (первый-> последний): данные 310 Данные 444 Данные 595. Данные 702. Данные 725
Одиночная инверсия списка:
открытый класс SingleLinkedListreverse {public static void main (string [] args) {node head = new Node (0); Узел Temp = null; Узлы cur = null; for (int i = 1; i <= 10; i ++) {temp = new Node (i); if (i == 1) {head.setNext (temp); } else {cur.setnext (temp); } cur = temp; } // 10.next = null; Узел H = голова; while (h! = null) {System.out.print (h.getdata () + "/t"); h = h.getnext (); } System.out.println (); // инвертировать 1 // h = node.reverse1 (head); // while (h! = null) {// system.out.print (h.getdata () + "/t"); // h = h.getnext (); //} // инвертировать 2 h = node.reverse1 (head); while (h! = null) {System.out.print (h.getdata () + "/t"); h = h.getnext (); }}}/** Каждый узел одного связанного списка содержит атрибуты, указывающие на следующий узел*/class node {объект Data; // Узел объекта данных Next; // Next Node Node (объект D) {this.data = d; } Node (объект D, узлы n) {this.data = d; this.next = n; } public Object getData () {return Data; } public void setData (data Object) {this.Data = data; } public node getNext () {return Next; } public void setNext (node next) {this.next = Next; } // МЕТОД 1 головка сброса Статического узла Обратный1 (головка узла) {node p = null; // новая голова после инверсионного узла Q = голова; // Результат вращения: 012,123,234, ...... 10 NULL NULL WHEN (HEAD.NEXT! = NULL) {P = HEAD.NEXT; // первый заменяется вторым, а затем P представляет Next Head.next = P.Next; // Второй заменяется третьим, а следующий, который уже достиг первой позиции, станет первой, и первая станет первой; // новый заменяется первым} return p; } // Method 2 Head не сбрасывает статический узел reample2 (head узла) {// указать указатель промежуточного узла к предыдущему узлу, вы все равно можете продолжать пересекать связанный список назад узел P1 = Head, P2 = Head.next, P3; // спереди, средний и задний/вращение Результат: 012, 123, 234, 345, 456 .... 9 10 NULL Where (P2! = NULL) {P3 = P2.next; p2.next = p1; // укажите назад и укажите вперед P1 = P2; // 2, 3 движутся вперед P2 = P3; } head.next = null; // голова не изменилась. Когда выход достигает 0, запросить 0.next на 1 возврат P1; }}