предисловие
Нижележащий фундамент определяет развитие верхнего слоя.
Как глядя на точку, дайте мне знать, что вы беспокоитесь о технологии.
Эта серия статей GithubРасширенное руководство по серверной частиОн был включен, этот проект совершенствуется, добро пожаловать в звезду.
Превью этой серии:
1. Что такое связанный список?
связанный список также
线性表Одна из массивов в линейной таблице顺序结构, и на этот раз связанный список является линейным списком链式存储结构, которая представляет собой непоследовательную, непоследовательную структуру данных в памяти, состоящую из нескольких узлов. Он хранит данные и адрес следующего узла в каждом узле.Поле данных называется полем данных, а поле адреса называется полем указателя. Указатель делится на указатель-предшественник и указатель-последователь, которые используются для записи позиций предыдущего узла и следующего узла соответственно.Указатель: присваивание переменной указателю на самом деле является присвоением значения адреса переменной указателю, что можно рассматривать как ссылку в Java.
1.1 Односвязный список
Односвязный список, как следует из названия, представляет собой связанный список только с одним направлением.Из приведенного выше рисунка односвязный список состоит из нескольких узлов.Каждый узел разделен на две части, одна часть хранит данные, а другая часть сохраняет местоположение следующего узла. На картинках оранжевый квадрат называется数据域, который используется для хранения данных. Желтый квадрат называется指针域Следующий узел для хранения позиции рядом (注意是下一个节点的位置，不是下一个指针的位置), этот next также называется указателем преемника.
Глядя на картинку выше, можно увидеть два особых места, то есть первый узел и последний узел. мы также можем позвонить头结点,尾结点. Что такого особенного в этих двух узлах? То есть головной узел не может хранить никаких данных, так как это начало связанного списка, а указатель преемника хвостового узла указывает на ноль, что означает, что это последний узел связанного списка.
Головной узел: первый узел в связанном списке, головной узел не может хранить данные.
Головной указатель: указатель первого узла в связанном списке, который используется для хранения базового адреса связанного списка и является началом всего связанного списка.
Узел хвостового узла: последний узел в связанном списке, указывая на пустую нулю, что означает, что это последний узел связанного списка.
1.2 Односторонний круговой связанный список
Односвязный список является производным от односвязного списка.Единственная разница между ним и односвязным списком заключается в том, что указатель-последователь хвостового узла односвязного списка указывает на ноль, а указатель-последователь хвостового узла односвязный список указывает на головной узел. Этот сквозной односвязный список называется单向循环链表. Преимущество кругового связанного списка состоит в том, что удобнее переходить от конца цепочки к ее началу, и он больше подходит для решения проблем кольцевой структуры, таких как знаменитыйПроблема Джозефа.
1.3 вдвойне связанный список
双向链表稍微复杂一些，它和单向链表相比除了后继指针以外还多了个前驱指针。 If the same amount of data is stored, a doubly linked list takes up more space than a singly linked list. Although two pointers in a doubly linked list are a waste of space, they can support bidirectional traversal and bring more flexibility to the linked list сам.
1.4 Дважды циклический связанный список
После понимания циклического связанного списка и двусвязного списка комбинация этих двух представляет собой двусторонний циклический связанный список.Вы можете видеть, что указатель-предшественник головного узла указывает на хвостовой узел, а указатель-последователь хвоста узел указывает на головной узел. Я не буду вводить здесь слишком много, все знают, какие бывают связанные списки.
2. Связанный список против массива
После долгого разговора о связанном списке, я не знаю, все ли это понимают, но мне самому стало очень скучно. Но основа такова: только изучив основы, вы сможете подняться выше. Теперь давайте посмотрим на разницу между связанным списком и массивом, о котором мы говорили ранее. Прежде всего, структуры хранения двух различны.Массив представляет собой последовательную структуру хранения, что означает, что это непрерывное пространство хранения в памяти, в то время как связанный список представляет собой цепную структуру хранения, то есть несмежную. Посмотрим, как они поведут себя в памяти:
Я думаю, что по картинкам вы уже увидели разницу.Поскольку массив представляет собой непрерывную структуру хранения, данные в массиве могут быть предварительно прочитаны с помощью механизма кэширования ЦП, поэтому эффективность доступа выше. Связанный список не хранится постоянно в памяти, поэтому он не удобен для кеша ЦП, и нет возможности эффективно читать вперед. Из-за разных структур данных временная сложность операций, таких как вставка, удаление и произвольный доступ к массивам и связанным спискам, прямо противоположна.
| множество | связанный список | |
|---|---|---|
| вставить, удалить | O(n) |
O(1) |
| произвольный доступ | O(1) |
O(n) |
Связанный список естественно поддерживает динамическое расширение, потому что он не создает пространство памяти заранее, а открывает пространство памяти только тогда, когда он фактически используется. Недостаток массивов в том, что они имеют фиксированный размер. Слишком много приложений расточительны. Если приложений слишком мало, то приходится часто расширять и перемещать массив. Если объем данных большой, это займет много времени. Поэтому при использовании списка, если вы можете заранее оценить размер данных, лучше указать размер во время инициализации, чтобы избежать влияния перемещения данных во время расширения.
3. Основные операции со связанными списками
3.1 Добавление связанного списка
Есть три случая операции добавления связанного списка:
-
добавить в голову
Добавление к головке разделено на два шага. Первый шаг - указать указатель преемника нового узла на исходный узел головки, а второй шаг - повернуть новый узел в узел головки. Это завершает дополнение заголовка.
-
увеличить до середины
Промежуточная вставка также делится на два этапа.Первый шаг — указать указатель преемника предыдущего узла в позиции вставки на новый узел, а второй шаг — указать указатель преемника нового узла на исходный узел. положения вставки.
-
добавить в конец
Вставить в конец связанного списка проще всего, просто укажите указатель преемника последнего узла на новый узел.
Давайте посмотрим на код, если у вас есть много времени, рекомендуется набрать его вручную, что даст вам более глубокое понимание.
/**
* @author: lixiaoshuang
* @create: 2019-12-08 23:11
**/
public class LinkedListAddDemo {
//头节点
private static Node headNode = null;
//尾节点
private static Node lastNode = null;
//链表的长度
private static int size;
public static void main(String[] args) {
//初始化一个链表
addByIndex(1, 0);
addByIndex(2, 1);
addByIndex(3, 2);
addByIndex(4, 3);
//头部插入
addByIndex(5, 0);
printNode(); //输出 5、1、2、3、4
//中间插入
addByIndex(5, 2);
printNode(); //输出 1、2、5、3、4
//尾部插入
addByIndex(5, 4);
printNode(); //输出 1、2、3、4、5
}
private static void addByIndex(int data, int index) {
if (index < 0 || index > size) {
throw new IndexOutOfBoundsException("超出链表节点范围");
}
Node node = new Node(data);
if (index == 0) {
//插入到头部
node.setNext(headNode);
headNode = node;
if (size == 0) {
lastNode = node;
}
} else if (index == size) {
//插入到尾部
lastNode.setNext(node);
lastNode = node;
} else {
//插入到中间
Node prevNode = get(index - 1);
Node nextNode = prevNode.getNext();
prevNode.setNext(node);
node.setNext(nextNode);
}
size++;
}
/**
* 通过位置查找链表节点
*
* @param index
* @return
*/
private static Node get(int index) {
if (index < 0 || index > size) {
throw new IndexOutOfBoundsException("超出链表节点范围");
}
Node temp = headNode;
for (int i = 0; i < index; i++) {
temp = temp.getNext();
}
return temp;
}
/**
* 打印节点
*/
private static void printNode() {
while (headNode != null) {
System.out.println(headNode.getDate());
headNode = headNode.getNext();
}
}
}
/**
* 定义一个节点
*
* @param <T>
*/
class Node<T> {
/**
* 节点中的数据
*/
private T date;
/**
* 下一个节点的指针
*/
private Node next;
public Node(T date) {
this.date = date;
}
public Node getNext() {
return next;
}
public void setNext(Node next) {
this.next = next;
}
public T getDate() {
return date;
}
public void setDate(T date) {
this.date = date;
}
}
3.2 Удаление связанного списка
Существует три случая удаления и добавления связанного списка:
-
удалить заголовок
Операция удаления заголовка должна только установить головной узел следующим узлом текущего головного узла.
-
удалить середину
Для удаления промежуточной операции необходимо только указать указатель-преемник предыдущего узла удаляемого узла на следующий узел удаляемого узла.
-
удалить хвост
Для удаления хвоста нужно только указать указатель преемника предпоследнего узла на ноль.
/**
* @author: lixiaoshuang
* @create: 2019-12-08 23:11
**/
public class LinkedListAddDemo {
//头节点
private static Node headNode = null;
//尾节点
private static Node lastNode = null;
//链表的长度
private static int size;
public static void main(String[] args) {
//初始化一个链表
addByIndex(1, 0);
addByIndex(2, 1);
addByIndex(3, 2);
addByIndex(4, 3);
//头部删除
delete(0);
printNode(); //输出 2、3、4
//尾部删除
delete(3);
printNode(); //输出 1、2、3
//中间删除
delete(2);
printNode(); //输出 1、2、4
}
/**
* 链表删除操作
*
* @param index
*/
private static void delete(int index) {
if (index < 0 || index >= size) {
throw new IndexOutOfBoundsException("超出链表节点范围");
}
if (index == 0) {
//删除头部
headNode = headNode.getNext();
} else if (index == size - 1) {
//删除尾部
Node prevNode = get(index - 1);
prevNode.setNext(null);
lastNode = prevNode;
} else {
//删除中间
Node prevNode = get(index - 1);
Node nextNode = prevNode.getNext().getNext();
prevNode.setNext(nextNode);
}
size--;
}
/**
* 通过位置查找链表节点
*
* @param index
* @return
*/
private static Node get(int index) {
if (index < 0 || index > size) {
throw new IndexOutOfBoundsException("超出链表节点范围");
}
Node temp = headNode;
for (int i = 0; i < index; i++) {
temp = temp.getNext();
}
return temp;
}
/**
* 打印节点
*/
private static void printNode() {
while (headNode != null) {
System.out.println(headNode.getDate());
headNode = headNode.getNext();
}
}
}
3.3 Модификация связанного списка
Изменение узла связанного списка напрямую заменяет узел, подлежащий изменению, новым узлом.Первый шаг — указать указатель преемника предыдущего узла измененного узла на новый узел, а затем указать указатель преемника нового узла на следующий узел измененного узла. Вот как изменить узел. Логика аналогична добавлению и удалению выше. Вот пример промежуточной модификации. Если вы хотите изменить данные в узле, не заменяя узел, это относительно просто, и вы можете реализовать это самостоятельно.
/**
* @author: lixiaoshuang
* @create: 2019-12-08 23:11
**/
public class LinkedListOperationDemo {
//头节点
private static Node headNode = null;
//尾节点
private static Node lastNode = null;
//链表的长度
private static int size;
public static void main(String[] args) {
//初始化一个链表
addByIndex(1, 0);
addByIndex(2, 1);
addByIndex(3, 2);
addByIndex(4, 3);
//修改头部
update(5, 0);
printNode(); //输出 5、2、3、4
//修改尾部
update(5, 3);
printNode(); //输出 1、2、3、5
//修改中间
update(5, 1);
printNode(); //输出 1、5、3、4
}
/**
* 链表的修改
*
* @param data
* @param index
*/
private static void update(int data, int index) {
if (index < 0 || index >= size) {
throw new IndexOutOfBoundsException("超出链表节点范围");
}
Node newNode = new Node(data);
if (index == 0) {
//修改头部
Node next = headNode.getNext();
newNode.setNext(next);
headNode = newNode;
} else if (index == size) {
//修改尾部
Node prevNode = get(index - 1);
prevNode.setNext(newNode);
lastNode = newNode;
} else {
//修改中间
Node prevNode = get(index - 1);
Node nextNode = prevNode.getNext().getNext();
prevNode.setNext(newNode);
newNode.setNext(nextNode);
}
}
/**
* 通过位置查找链表节点
*
* @param index
* @return
*/
private static Node get(int index) {
if (index < 0 || index > size) {
throw new IndexOutOfBoundsException("超出链表节点范围");
}
Node temp = headNode;
for (int i = 0; i < index; i++) {
temp = temp.getNext();
}
return temp;
}
/**
* 打印节点
*/
private static void printNode() {
while (headNode != null) {
System.out.println(headNode.getDate());
headNode = headNode.getNext();
}
}
}
3.4 Запрос связанного списка
Кстати, о запросе, не знаю, нашли ли вы его, код выше уже реализован😭, вот он выложен, давайте посмотрим:
/**
* 通过位置查找链表节点
*
* @param index
* @return
*/
private static Node get(int index) {
if (index < 0 || index > size) {
throw new IndexOutOfBoundsException("超出链表节点范围");
}
Node temp = headNode;
for (int i = 0; i < index; i++) {
temp = temp.getNext();
}
return temp;
}
4. Вопросы для интервью
4.1 Как определить, есть ли цикл в односвязном списке?
Здесь мы используем快慢指针Метод определения того, имеет ли связанный список цикл, сначала создайте два указателя, указывающих на головной узел связанного списка одновременно, медленный указатель выполняет один шаг, быстрый указатель выполняет два шага и оценивает, являются ли два указателя равны, если они равны, значит, есть цикл. Вот односторонний круговой связанный список, который мы представили выше. Пока связанный список имеет кольцо, то при его обходе с помощью быстрого и медленного указателей два указателя определенно будут равны (указатель здесь относится к узлу). Это как бегать в парке по выходным.Молодежь бегает быстрее,пожилые бегут медленнее,а молодежь догонит старика и перегонит его в определенном месте.Причина очень проста,потому что дорожка в парке это круг, ха-ха.
Посмотрите на код ниже Я сделал небольшую модификацию хвостовой вставки в операции вставки связанного списка, то есть, чтобы преемник каждого хвостового узла указывал на головной узел, таким образом превращая односвязный список в односторонний круговой связанный список.
/**
* @author: lixiaoshuang
* @create: 2019-12-08 23:11
**/
public class LinkedListOperationDemo {
//头节点
private static Node headNode = null;
//尾节点
private static Node lastNode = null;
//链表的长度
private static int size;
public static void main(String[] args) {
//初始化一个链表
addByIndex(1, 0);
addByIndex(2, 1);
addByIndex(3, 2);
addByIndex(4, 3);
//判断链表是否有环
boolean ringed = isRinged();
System.out.println(ringed); //输出为true
}
/**
* 判断链表是否有环
*
* @return
*/
private static boolean isRinged() {
if (headNode == null) {
return false;
}
//定义快慢指针
Node slowPointer, fastPointer;
slowPointer = fastPointer = headNode;
while (slowPointer != null && fastPointer != null) {
slowPointer = slowPointer.getNext();
fastPointer = fastPointer.getNext().getNext();
//如果两个指针有相等则有环
if (slowPointer == fastPointer) {
return true;
}
}
return false;
}
/**
* 链表插入操作
*
* @param data
* @param index
*/
private static void addByIndex(int data, int index) {
if (index < 0 || index > size) {
throw new IndexOutOfBoundsException("超出链表节点范围");
}
Node node = new Node(data);
if (index == 0) {
//插入到头部
node.setNext(headNode);
headNode = node;
if (size == 0) {
lastNode = node;
}
} else if (index == size) {
//插入到尾部
lastNode.setNext(node);
lastNode = node;
node.setNext(headNode); //这里尾部插入将最后一个节点的后继指向头节点，这样链表就是循环链表了。
} else {
//插入到中间
Node prevNode = get(index - 1);
Node nextNode = prevNode.getNext();
prevNode.setNext(node);
node.setNext(nextNode);
}
size++;
}
}
4.2 Как перевернуть связанный список?
Это тоже вопрос высокочастотного собеседования.Способ реализации здесь писать не буду.Оставлю вам вопрос на размышление.Друзья у кого есть время могут попробовать решить его самостоятельно.Хотя этот вопрос решается под Baidu,но все же Я надеюсь, что вы сначала подумаете об этом сами, а если уж совсем не додумаетесь, поищите решение проблемы. Вы также можете перейти кСтруктуры данных и алгоритмы, разрывающие руки"Чтобы просмотреть исходный код, я выбил его вручную.
5. Ссылка
«Комический алгоритм»
«Красота структур данных и алгоритмов»
«Структура данных Dahua»
6. Конец
На мой взгляд, есть три базовых знания, которые должны усвоить бэкенд-программисты."数据结构与算法","计算机系统","操作系统Linux". Разве мы не носим достаточно одежды в эту интернет-зимнюю эпоху? всю ночь не спал(纯属扯淡，哈哈) решил привести всех к совместному изучению трех базовых знаний.Открывающая серия этой серии - «Структуры данных и алгоритмы разрыва рук».После завершения каждой серии будет открыта следующая серия, так что не волнуйтесь. Вы можете обратить внимание на мой официальный аккаунт, продолжайте следить и учиться.
Эта серия статей GithubРасширенное руководство по серверной частиОн был включен, этот проект совершенствуется, добро пожаловать в звезду.
Все статьи в официальном аккаунте написаны авторами блогов и будут постоянно обновляться. Если вы хотите стать свидетелем или расти вместе с блоггерами, добро пожаловать на внимание!
Наконец, я вижу, что у всех друзей здесь есть этот дух готовности учиться. Спасибо, что читаете статьи, которые я написал. Блогеры не очень хорошо умеют подводить итоги. Если у вас есть какие-либо вопросы, пожалуйста, оставьте сообщение, чтобы исправить их.Нравится, следуй. На пути к написанию мне нужна поддержка всех старых утюгов.Ваша поддержка-движущая сила для следующей статьи.