data-structures
Связанный список
Поиск…
Введение в связанные списки
Связанный список представляет собой линейный набор элементов данных, называемых узлами, которые связаны с другим узлом (узлами) с помощью «указателя». Ниже приведен одиночный список с указанием главы.
┌─────────┬─────────┐ ┌─────────┬─────────┐
HEAD ──▶│ data │"pointer"│──▶│ data │"pointer"│──▶ null
└─────────┴─────────┘ └─────────┴─────────┘
Существует много типов связанных списков, в том числе однократно и дважды связанных списков и круговых связанных списков.
преимущества
Связанные списки - это динамическая структура данных, которая может расти и сокращаться, выделять и освобождать память во время работы программы.
Операции ввода и удаления узлов легко реализуются в связанном списке.
Линейные структуры данных, такие как стеки и очереди, легко реализуются со связанным списком.
Связанные списки могут сократить время доступа и могут расширяться в реальном времени без накладных расходов.
Одиночный список
Отдельно связанные списки - это тип связанного списка . Узлы с узлом связанного списка имеют только один «указатель» на другой узел, обычно «следующий». Он называется односвязным списком, потому что каждый узел имеет только один «указатель» на другой узел. У одного связанного списка может быть ссылка на голову и / или хвост. Преимущество наличия ссылки на хвост - это getFromBack , addToBack и removeFromBack , которые становятся O (1).
┌─────────┬─────────┐ ┌─────────┬─────────┐
HEAD ──▶│ data │"pointer"│──▶│ data │"pointer"│──▶ null
└─────────┴────△────┘ └─────────┴─────────┘
SINGLE │
REFERENCE ────┘
Пример кода на Java, с модульными тестами - одноуровневый список с указанием главы
Связанный список XOR
Связанный список XOR также называется списком, связанным с памятью . Это еще одна форма двусвязного списка. Это сильно зависит от логики логики XOR и ее свойств.
Почему это называется «Эффективный связанный с памятью список»?
Это называется так, потому что это использует меньше памяти, чем традиционный двусвязный список.
Разве это отличается от двусвязного списка?
Да , это так.
В Doubly-Linked List хранятся два указателя, которые указывают на следующий и предыдущий узел. В принципе, если вы хотите вернуться назад, вы переходите к адресу, указанному back указателем. Если вы хотите идти вперед, вы переходите к адресу, указанному next указателем. Это как:
Эффективный связанный с памятью список , а именно связанный список XOR имеет только один указатель вместо двух. В этом сохранен предыдущий адрес (addr (prev)) XOR (^) следующий адрес (addr (следующий)). Когда вы хотите перейти к следующему узлу, вы выполняете определенные вычисления и находите адрес следующего узла. Это то же самое для перехода к предыдущему узлу. Это как:
Как это работает?
Чтобы понять, как работает связанный список, вам нужно знать свойства XOR (^):
|-------------|------------|------------|
| Name | Formula | Result |
|-------------|------------|------------|
| Commutative | A ^ B | B ^ A |
|-------------|------------|------------|
| Associative | A ^ (B ^ C)| (A ^ B) ^ C|
|-------------|------------|------------|
| None (1) | A ^ 0 | A |
|-------------|------------|------------|
| None (2) | A ^ A | 0 |
|-------------|------------|------------|
| None (3) | (A ^ B) ^ A| B |
|-------------|------------|------------|
Теперь давайте оставим это в стороне и посмотрим, что каждый узел хранит.
Первый узел, или голова , сохраняет 0 ^ addr (next) поскольку нет предыдущего узла или адреса. Похоже на это .
Затем второй узел хранит addr (prev) ^ addr (next) . Похоже на это .
Хвост списка не имеет следующего узла, поэтому он хранит addr (prev) ^ 0 . Похоже на это .
Переход от головы к следующему узлу
Предположим, вы сейчас на первом узле или на узле A. Теперь вы хотите переместиться в узел B. Это формула для этого:
Address of Next Node = Address of Previous Node ^ pointer in the current Node
Так было бы:
addr (next) = addr (prev) ^ (0 ^ addr (next))
Поскольку это голова, предыдущий адрес был бы просто 0, поэтому:
addr (next) = 0 ^ (0 ^ addr (next))
Мы можем удалить круглые скобки:
addr (next) = 0 ^ 0 addr (next)
Используя свойство none (2) , можно сказать, что 0 ^ 0 всегда будет 0:
addr (next) = 0 ^ addr (next)
Используя свойство none (1) , мы можем упростить его:
addr (next) = addr (next)
Вы получили адрес следующего узла!
Переход от узла к следующему узлу
Теперь предположим, что мы находимся в среднем узле, у которого есть предыдущий и следующий узел.
Применим формулу:
Address of Next Node = Address of Previous Node ^ pointer in the current Node
Теперь замените значения:
addr (next) = addr (prev) ^ (addr (prev) ^ addr (next))
Удалить круглые скобки:
addr (next) = addr (prev) ^ addr (prev) ^ addr (next)
Используя свойство none (2) , мы можем упростить:
addr (next) = 0 ^ addr (next)
Используя свойство none (1) , мы можем упростить:
addr (next) = addr (next)
И ты понял!
Переход от узла к узлу, на котором вы были раньше
Если вы не понимаете заголовок, это в основном означает, что если вы были на узле X и теперь переместились на узел Y, вы хотите вернуться к узлу, посещенному ранее или в основном узлу X.
Это не громоздкая задача. Помните, что я упомянул выше, что вы храните адрес, на котором вы были во временной переменной. Таким образом, адрес узла, который вы хотите посетить, лежит в переменной:
addr (prev) = temp_addr
Переход от узла к предыдущему узлу
Это не то же самое, что указано выше. Я хочу сказать, что вы были на узле Z, теперь вы находитесь в узле Y и хотите перейти к узлу X.
Это почти так же, как переход от узла к следующему узлу. Просто это все наоборот. Когда вы пишете программу, вы будете использовать те же шаги, что я упомянул при переходе от одного узла к следующему узлу, просто чтобы найти более ранний элемент в списке, чем найти следующий элемент.
Пример кода в C
/* C/C++ Implementation of Memory efficient Doubly Linked List */
#include <stdio.h>
#include <stdlib.h>
// Node structure of a memory efficient doubly linked list
struct node
{
int data;
struct node* npx; /* XOR of next and previous node */
};
/* returns XORed value of the node addresses */
struct node* XOR (struct node *a, struct node *b)
{
return (struct node*) ((unsigned int) (a) ^ (unsigned int) (b));
}
/* Insert a node at the begining of the XORed linked list and makes the
newly inserted node as head */
void insert(struct node **head_ref, int data)
{
// Allocate memory for new node
struct node *new_node = (struct node *) malloc (sizeof (struct node) );
new_node->data = data;
/* Since new node is being inserted at the begining, npx of new node
will always be XOR of current head and NULL */
new_node->npx = XOR(*head_ref, NULL);
/* If linked list is not empty, then npx of current head node will be XOR
of new node and node next to current head */
if (*head_ref != NULL)
{
// *(head_ref)->npx is XOR of NULL and next. So if we do XOR of
// it with NULL, we get next
struct node* next = XOR((*head_ref)->npx, NULL);
(*head_ref)->npx = XOR(new_node, next);
}
// Change head
*head_ref = new_node;
}
// prints contents of doubly linked list in forward direction
void printList (struct node *head)
{
struct node *curr = head;
struct node *prev = NULL;
struct node *next;
printf ("Following are the nodes of Linked List: \n");
while (curr != NULL)
{
// print current node
printf ("%d ", curr->data);
// get address of next node: curr->npx is next^prev, so curr->npx^prev
// will be next^prev^prev which is next
next = XOR (prev, curr->npx);
// update prev and curr for next iteration
prev = curr;
curr = next;
}
}
// Driver program to test above functions
int main ()
{
/* Create following Doubly Linked List
head-->40<-->30<-->20<-->10 */
struct node *head = NULL;
insert(&head, 10);
insert(&head, 20);
insert(&head, 30);
insert(&head, 40);
// print the created list
printList (head);
return (0);
}
Вышеприведенный код выполняет две основные функции: вставку и трансверсальность.
Вставка: выполняется с помощью функции
insert. Это вставляет новый узел в начале. Когда эта функция вызывается, она помещает новый узел в качестве главы, а предыдущий головной узел - в качестве второго узла.Обход: это выполняется функцией
printList. Он просто проходит через каждый узел и выводит значение.
Обратите внимание, что XOR указателей не определяется стандартом C / C ++. Таким образом, описанная выше реализация может не работать на всех платформах.
Рекомендации
https://cybercruddotnet.wordpress.com/2012/07/04/complicating-things-with-xor-linked-lists/
http://www.ritambhara.in/memory-efficient-doubly-linked-list/comment-page-1/
http://www.geeksforgeeks.org/xor-linked-list-a-memory-efficient-doubly-linked-list-set-2/
Обратите внимание, что я взял много контента из своего собственного ответа по основному.
Пропустить Список
Пропущенные списки - это связанные списки, которые позволяют вам перейти к правильному узлу. Это метод, который быстрее, чем обычный одиночный список. Это в основном односвязный список, но указатели не идут от одного узла к следующему узлу, а пропускают несколько узлов. Таким образом, имя «Пропустить список».
Разве это отличается от единого связанного списка?
Да , это так.
Единосвязанный список - это список с каждым узлом, указывающим на следующий узел. Графическое представление односвязного списка выглядит так:
Список пропусков - это список с каждым узлом, указывающим на узел, который может или не может быть после него. Графическое представление списка пропусков:
Как это работает?
Список пропусков прост. Предположим, мы хотим получить доступ к узлу 3 в приведенном выше изображении. Мы не можем идти по пути от головы к четвертому узлу, так как это происходит после третьего узла. Итак, мы идем от головы ко второму узлу, а затем к третьему.
Графическое представление выглядит так:
Рекомендации
Дважды связанный список
Двунаправленные списки - это тип связанного списка . Узлы с двойным соединением имеют два «указателя» для других узлов: «следующий» и «предыдущий». Он называется двойным связанным списком, поскольку каждый узел имеет только два «указателя» для других узлов. У двусвязного списка может быть указатель на голову и / или хвост.
┌─────────┬─────────┬─────────┐ ┌─────────┬─────────┬─────────┐
null ◀──┤previous │ data │ next │◀──┤previous │ data │ next │
│"pointer"│ │"pointer"│──▶│"pointer"│ │"pointer"│──▶ null
└─────────┴─────────┴─────────┘ └─────────┴─────────┴─────────┘
▲ △ △
HEAD │ │ DOUBLE │
└──── REFERENCE ────┘
Сопоставленные списки менее эффективны по сравнению с отдельными списками; однако для некоторых операций они значительно улучшают эффективность времени. Простым примером является функция get , которая для двусвязного списка с заголовком и хвостом будет начинаться с головы или хвоста в зависимости от индекса элемента для его получения. Для n списка -элементного, чтобы получить n/2 + i индексироваться элементом, одиночно связанный список с головой / ссылка хвоста должна пройти n/2 + i узлы, поскольку он не может «вернуться» от хвоста. В двусвязном списке с заголовком / хвостом ссылки должны проходить только узлы n/2 - i , поскольку они могут «возвращаться» из хвоста, перемещая список в обратном порядке.
Основной пример SinglyLinkedList в Java
Основная реализация для односвязного списка в java - может добавлять целочисленные значения в конец списка, удалять первое значение, полученное из списка, возвращать массив значений в данный момент времени и определять, присутствует ли данное значение в списке.
Node.java
package com.example.so.ds;
/**
* <p> Basic node implementation </p>
* @since 20161008
* @author Ravindra HV
* @version 0.1
*/
public class Node {
private Node next;
private int value;
public Node(int value) {
this.value=value;
}
public Node getNext() {
return next;
}
public void setNext(Node next) {
this.next = next;
}
public int getValue() {
return value;
}
}
SinglyLinkedList.java
package com.example.so.ds;
/**
* <p> Basic single-linked-list implementation </p>
* @since 20161008
* @author Ravindra HV
* @version 0.2
*/
public class SinglyLinkedList {
private Node head;
private volatile int size;
public int getSize() {
return size;
}
public synchronized void append(int value) {
Node entry = new Node(value);
if(head == null) {
head=entry;
}
else {
Node temp=head;
while( temp.getNext() != null) {
temp=temp.getNext();
}
temp.setNext(entry);
}
size++;
}
public synchronized boolean removeFirst(int value) {
boolean result = false;
if( head == null ) { // or size is zero..
// no action
}
else if( head.getValue() == value ) {
head = head.getNext();
result = true;
}
else {
Node previous = head;
Node temp = head.getNext();
while( (temp != null) && (temp.getValue() != value) ) {
previous = temp;
temp = temp.getNext();
}
if((temp != null) && (temp.getValue() == value)) { // if temp is null then not found..
previous.setNext( temp.getNext() );
result = true;
}
}
if(result) {
size--;
}
return result;
}
public synchronized int[] snapshot() {
Node temp=head;
int[] result = new int[size];
for(int i=0;i<size;i++) {
result[i]=temp.getValue();
temp = temp.getNext();
}
return result;
}
public synchronized boolean contains(int value) {
boolean result = false;
Node temp = head;
while(temp!=null) {
if(temp.getValue() == value) {
result=true;
break;
}
temp=temp.getNext();
}
return result;
}
}
TestSinglyLinkedList.java
package com.example.so.ds;
import java.util.Arrays;
import java.util.Random;
/**
*
* <p> Test-case for single-linked list</p>
* @since 20161008
* @author Ravindra HV
* @version 0.2
*
*/
public class TestSinglyLinkedList {
/**
* @param args
*/
public static void main(String[] args) {
SinglyLinkedList singleLinkedList = new SinglyLinkedList();
int loop = 11;
Random random = new Random();
for(int i=0;i<loop;i++) {
int value = random.nextInt(loop);
singleLinkedList.append(value);
System.out.println();
System.out.println("Append :"+value);
System.out.println(Arrays.toString(singleLinkedList.snapshot()));
System.out.println(singleLinkedList.getSize());
System.out.println();
}
for(int i=0;i<loop;i++) {
int value = random.nextInt(loop);
boolean contains = singleLinkedList.contains(value);
singleLinkedList.removeFirst(value);
System.out.println();
System.out.println("Contains :"+contains);
System.out.println("RemoveFirst :"+value);
System.out.println(Arrays.toString(singleLinkedList.snapshot()));
System.out.println(singleLinkedList.getSize());
System.out.println();
}
}
}