Связанный список - это сложная структура данных. Отношение между данными составляет связанный список, разделенный на три типа: один связанный список, круговой связанный список и двунаправленный связанный список . Следующее будет представлено один за другим. Связанные списки являются основными и важными точками знаний в структуре данных. Здесь мы поговорим о реализации связанных списков в Java.
Java Linked Rist Operations: Список с одним связанными и списками с двумя связанными
Несколько очков в основном говорят:
1. Введение в связанный список
2. Принципы и потребности для реализации связанных списков
3. Одноцепочечный пример
4. Двойной пример
1. Введение в связанный список
Связанные списки являются относительно распространенной структурой данных. Хотя связанные списки более сложны для хранения, они более удобны при запросе. Они используются в нескольких компьютерных языках соответственно. Есть много категорий связанных списков. Статьи анализируются на одно связанные списки и списки с двумя связанными. Данные в связанном списке все равно, что подключаться к цепочке, позволяя легкому доступ к данным.
2. Принципы и потребности для реализации связанных списков
Здесь анализируются только односвященные списки и списки с двумя связанными. Процесс реализации связанных списков немного сложный, но он принесет много преимуществ. Например, с прибытием онлайн -покупок продавцы обычно упаковывают товары в коробку и пишут информацию о адресах в коробке. Express Company может найти покупателя через информацию на коробке, а товары прибывают нетронутыми. Без защиты коробки продукт может быть поврежден по пути. Связанный список похож на поле с написанной информацией о адресах, которая не только защищает информацию о продукте, но и записывает логистическую информацию. В связанном списке есть головкий узел, аналогичный «локомотиву». Пока найдено соответствующий узел головки, вы можете работать в связанном списке. В этом анализе головный узел действует только как заголовок данных и не сохраняет допустимые данные.
Принцип реализации одного связанного списка показан на рисунке:
Двойной связанный принцип внедрения списка:
3. Одноцепочечный пример
ICompoerate <t> класс работы интерфейса:
Package linklistSt; import java.util.map; public interface icommoperate <t> {public boolean insertnode (t node); Общественный логический вставка (int pos, t node); public boolean deleteNode (int pos, map <string, object> map); public void printlink ();}Одиночный узел списка:
пакет LinkListStest; // Один подключенный таблица узлы открытого класса Snode {Private String Data; Приватный Snode NextNode; public snode () {} public snode (string data) {this.data = data; this.nextnode = new snode (); } public String getData () {return data; } public void setData (String Data) {this.Data = data; } public snode getNextNode () {return nextNode; } public void setNextNode (snode nextNode) {this.NextNode = nextNode; } @Override public String toString () {return "snode [data =" + data + "]"; }}Операция по одной ссылке:
Package linklisttest; import java.util.hashmap; import java.util.map; открытый класс SingleLinklist реализует Icomperate <node> {private snode head = new snode ("head"); // Общественный указатель заголовка, без изменений после объявления private int size = 0; public int getSize () {return this.size; } / * * Вставьте связанный список, вставляйте его до конца каждый раз * / @Override public boolean insertnode (snode node) {boolean flag = false; Snode Current = this.head; if (this.size == 0) {// пустой связанный список this.head.setnextnode (node); node.setnextnode (null); } else {// Узел в связанном списке while (current.getNextNode ()! = null) {current = current.getNextNode (); } current.setNextNode (node); node.setnextnode (null); } this.size ++; flag = true; вернуть флаг; } / * * Вставьте указанную позицию POS в связанный список, начиная с 1, а POS больше, чем размер, затем вставьте конец связанного списка * * / @override public boolean insertposnode (int pos, snode node) {boolean flag = true; Snode Current = this.head.getNextNode (); if (this.size == 0) {// пустой связанный список this.head.setnextnode (node); node.setnextnode (null); this.size ++; } else if (this.size <pos) {// положение POS больше, чем длина связанного списка, insertNode (node); } else if (pos> 0 && pos <= this.size) {// Узел в связанном списке // 1. Найдите узел и передний узел, который будет вставлен int find = 0; Snode prenode = this.head; // передний узел SNODE CurrentNode = Current; // текущий узел while (найти <pos-1 && currentNode.getNextNode ()! = Null) {prenode = current; // передний узел перемещается назад currentNode = currentNode.getNextNode (); // текущий узел перемещается назад на Find ++; } // System.out.println (prenode); // system.out.println (currentNode); // 2. Вставьте узел prenode.setnextnode (node); node.setnextnode (currentNode); this.size ++; System.out.println («Узел был вставлен в связанный список»); } else {System.out.println ("Информация о позиции"); flag = false; } вернуть флаг; } / * * Укажите узел POS связанного списка и удалите соответствующий узел. Метод: найти передние и задние узлы, чтобы удалить и удалить. Начиная с 1 * */ @Override public boolean deleteNode (int pos) {boolean flag = false; Snode Current = this.head.getNextNode (); if (pos <= 0 || pos> this.size || current == null) {system.out.println ("ошибка информации о положении или нет информации в связанном списке"); } else {// 1. Найдите передние и задние узлы, чтобы удалить int find = 0; Snode prenode = this.head; // Front Node Snode nextNode = current.getNextNode (); // обратный узел while (найти <pos-1 && nextnode.getNextNode ()! = Null) {prenode = current; // передний узел перемещается обратно nextNode = nextNode.getNextNode (); // задний узел перемещается обратно находить ++; } // System.out.println (prenode); // system.out.println (nextnode); // 2. Удалить узел prenode.setNextNode (nextNode); System.gc (); это. size--; flag = true; } вернуть флаг; } / * * Укажите узел POS в связанном списке и измените соответствующий узел. Начиная с 1 * */ @Override public boolean updateNode (int pos, map <string, object> map) {boolean flag = false; Snode node = getNode (pos, map); // Получить узел в соответствующей позиции if (node! = Null) {string data = (string) map.get ("data"); node.setdata (data); flag = true; } вернуть флаг; } / * * Найти узл POS указанного списка, начиная с 1 * * / @Override public snode getNode (int pos, map <string, object> map) {snode current = this.head.getNextNode (); if (pos <= 0 || pos> this.size || current == null) {System.out.println ("Информация о позиции неверна или связанный список не существует"); вернуть ноль; } int find = 0; while (find <pos-1 && current! = null) {current = current.getNextNode (); найти ++; } вернуть ток; } / * * Печать связанный список * * / @Override public void printlink () {int length = this.size; if (длина == 0) {System.out.println ("Связанный список пуст!"); возвращаться ; } Snode current = this.head.getNextNode (); int find = 0; System.out.println («Общее количество узлов:« + длина + »); while (current! = null) {System.out.println ("th" + (++ find) + "узлы:" + current); current = current.getNextNode (); }} public static void main (string [] args) {singleLinklist sll = new singlelinklist (); Snode node1 = new Snode ("node1"); SNODE NODE2 = новый SNODE ("NODE2"); Snode Node3 = новый Snode ("Node3"); Snode node4 = новый Snode ("node4"); Snode Node5 = новый Snode ("Node5"); SNODE NODE6 = новый SNODE («Вставьте указанное положение»); sll.insertposnode (sll.getSize ()+1, node1); sll.insertposnode (sll.getSize ()+1, node2); sll.insertposnode (sll.getSize ()+1, node3); sll.insertposnode (sll.getSize ()+1, node4); sll.insertposnode (sll.getSize ()+1, node5); // sll.insertnode (node1); // sll.insertnode (node2); // sll.insertnode (node3); // sll.insertnode (node4); // sll.insertnode (node5); System.out.println ("**********************************); sll.printlink (); System.out.println ("******************************* '); int pos = 2; System.out.println («Получить данные"+pos+"данные положения связанного списка:"+sll.getNode (pos, null)); System.out.println ("****************************** Вставьте узлы в указанное положение связанного списка ********************************* '); int pos1 = 2; System.out.println («Вставьте данные в«+pos1+»узлы:»); sll.insertposnode (pos1, node6); sll.printlink (); System.out.println ("************************************** int pos2 = 2; System.out.println ("удалить"+pos2+"узлы:"); sll.deletenode (pos2); sll.printlink (); System.out.println ("*************************************** int pos3 = 2; System.out.println («изменить узлы«+pos3+»:»); Map <string, object> map = new hashmap <> (); map.put («data», «это тест»); sll.updatenode (pos3, map); sll.printlink (); }}4. Двойной пример
ICompoerate <t> класс работы интерфейса:
Package linklistSt; import java.util.map; public interface icommoperate <t> {public boolean insertnode (t node); Общественный логический вставка (int pos, t node); public boolean deleteNode (int pos, map <string, object> map); public void printlink ();}Узел списка с двойным связью:
Package linklistStest; // Двойной сосудистый узел Таблица Общедоступный класс dnode {private dnode priornode; частные строковые данные; private dnode nextnode; public dnode () {} public dnode (String Data) {this.priornode = new dnode (); this.data = data; this.nextnode = new dnode (); } public dnode getPriOrnode () {return priOrnode; } public void setPriornode (dnode priornode) {this.priornode = priornode; } public String getData () {return data; } public void setData (String Data) {this.Data = data; } public dnode getNextNode () {return nextNode; } public void setNextNode (dnode nextNode) {this.NextNode = nextNode; } @Override public String toString () {return "dnode [data =" + data + "]"; }}Класс реализации списка с двойным списком:
Package linklisttest; import java.util.hashmap; import java.util.map; открытый класс DoubleLinkList реализует iCommoperate <dnode> {private dnode head = new dnode ("head"); private int size = 0; public int getSize () {return this.size; } / * * Вставьте связанный список, вставляйте его до конца каждый раз * * / @Override public boolean insertnode (dnode node) {boolean flag = false; Dnode current = this.head; if (this.size == 0) {// пустой связанный список this.head.setnextnode (node); node.setpriornode (this.head); node.setnextnode (null); } else {// Узел в связанном списке while (current.getNextNode ()! = null) {current = current.getNextNode (); } current.setNextNode (node); node.setnextnode (null); node.setpriornode (current); } this.size ++; flag = true; вернуть флаг; } / * * Вставьте указанную позицию POS в связанный список, начиная с 1, а POS больше, чем размер, вставьте конец связанного списка * * / @@override public boolean insertposnode (int pos, dnode node) {boolean flag = true; Dnode current = this.head.getNextNode (); if (this.size == 0) {// Связанный список пуст this.head.setnextnode (node); node.setnextnode (null); node.setpriornode (this.head); this.size ++; } else if (pos> this.size) {// pos position больше, чем длина связанного списка, вставьте End InSertNode (Node); } else if (pos> 0 && pos <= this.size) {// Узел в связанном списке // 1. Найдите вставлен POS -узел, вставьте место для тока узела POS int find = 0; while (find <pos-1 && current.getNextNode ()! = null) {current = current.getNextNode (); найти ++; } // 2. Вставьте узел if (current.getNextNode () == null) {// hail node.setpriorornode (current); node.setnextnode (null); current.setNextNode (узлы); } else if (current.getNextNode ()! = null) {// Intermediate Node Node.setPriornode (current.getPriornode ()); node.setnextnode (current); current.getpriornode (). setNextNode (node); current.setpriornode (узел); } this.size ++; } else {System.out.println ("Информация о позиции"); flag = false; } вернуть флаг; } / * * Укажите узел POS в связанном списке, удалите соответствующий узел, начиная с 1 * * / @Override public boolean deleteNode (int pos) {boolean flag = false; Dnode current = this.head.getNextNode (); if (pos <= 0 || pos> this.size || current == null) {System.out.println ("Информация о позиции неверна или связанный список не существует"); } else {// 1. Найдите местоположение, которое будет удалено pos node int sind = 0; while (find <pos-1 && current.getNextNode ()! = null) {current = current.getNextNode (); найти ++; } // 2. Удалить узел if (current.getNextNode () == null) {// Хейп -узл current.getPriornode (). SetNextNode (null); } else if (current.getNextNode ()! = null) {// Промежуточный узел current.getPriornode (). setNextNode (current.getNextNode ()); current.getNextNode (). setPriOrnode (current.getPriornode ()); } System.gc (); это. size--; flag = true; } вернуть флаг; } / * * Укажите узел POS в связанном списке и измените соответствующий узел. Начните с 1 * */ @Override public boolean updateNode (int pos, map <string, object> map) {boolean flag = false; Dnode node = getNode (pos, map); if (node! = null) {string data = (string) map.get ("data"); node.setdata (data); flag = true; } вернуть флаг; } / * * Найдите узл POS указанного списка, запускаясь в 1 * * / @Override public dnode getNode (int pos, map <string, object> map) {dnode current = this.head.getNextNode (); if (pos <= 0 || pos> this.size || current == null) {System.out.println ("Информация о позиции неверна или связанный список не существует"); вернуть ноль; } int find = 0; while (find <pos-1 && current! = null) {current = current.getNextNode (); найти ++; } вернуть ток; } / * * Печать связанный список * * / @Override public void printlink () {int length = this.size; if (длина == 0) {System.out.println ("Связанный список пуст!"); возвращаться ; } Dnode current = this.head.getNextNode (); int find = 0; System.out.println («Общее количество узлов:« + длина + »); while (current! = null) {System.out.println ("th" + (++ find) + "узлы:" + current); current = current.getNextNode (); }} public static void main (string [] args) {doubleLinklist dll = new DoubleLinkList (); Dnode node1 = new dnode ("node1"); Dnode node2 = new dnode ("node2"); Dnode node3 = new dnode ("node3"); Dnode node4 = new dnode ("node4"); Dnode node5 = new dnode ("node5"); Dnode node6 = new dnode ("вставьте указанное положение"); dll.insertposnode (10, node1); dll.insertposnode (10, node2); dll.insertposnode (10, node3); dll.insertposnode (10, node4); dll.insertposnode (10, node5); // dll.insertnode (node1); // dll.insertnode (node2); // dll.insertnode (node3); // dll.insertnode (node4); // dll.insertnode (node5); System.out.println ("**********************************); dll.printlink (); System.out.println("************************************"); int pos = 2; System.out.println («Получить данные"+pos+"данные позиции связанного списка:"+dll.getNode (pos, null)); System.out.println ("****************************** Вставьте узлы в указанное положение связанного списка ********************************* '); int pos1 = 2; System.out.println («Вставить данные в узлы"+pos1+":"); dll.insertposnode (pos1, node6); dll.printlink (); System.out.println ("********************************* int pos2 = 7; System.out.println ("удалить"+pos2+"узлы:"); dll.deletenode (pos2); dll.printlink (); System.out.println ("************************************ Модифицировать узлы, указанные в связанном списке ********************************* int pos3 = 2; System.out.println («изменить узлы«+pos3+»:»); Map <string, object> map = new hashmap <> (); map.put («data», «это тест»); dll.updatenode (pos3, map); dll.printlink (); }}Спасибо за чтение, я надеюсь, что это поможет вам. Спасибо за поддержку этого сайта!