data-structures
연결된 목록
수색…
연결된 목록 소개
연결된 목록은 "포인터"를 통해 다른 노드에 연결된 노드라고하는 선형 데이터 요소 모음입니다. 다음은 헤드 참조가있는 단일 링크 목록입니다.
┌─────────┬─────────┐ ┌─────────┬─────────┐
HEAD ──▶│ data │"pointer"│──▶│ data │"pointer"│──▶ null
└─────────┴─────────┘ └─────────┴─────────┘
단일 목록 및 이중 연결 목록 및 순환 연결 목록을 포함하여 많은 유형의 연결 목록이 있습니다.
장점
링크 된 목록은 프로그램이 실행되는 동안 확장 및 축소, 할당 및 할당 취소 할 수있는 동적 데이터 구조입니다.
노드 삽입 및 삭제 작업은 링크 된 목록에서 쉽게 구현됩니다.
스택 및 대기열과 같은 선형 데이터 구조는 연결된 목록으로 쉽게 구현됩니다.
링크 된 목록은 액세스 시간을 줄일 수 있으며 메모리 오버 헤드없이 실시간으로 확장 될 수 있습니다.
단독으로 링크 된 목록
단일 연결리스트는의 유형 연결리스트 . 단일 링크 된 목록의 노드에는 다른 노드 (일반적으로 "다음")에 대한 하나의 "포인터"만 있습니다. 각 노드에는 다른 노드에 대한 "포인터"가 하나만 있기 때문에 단일 연결 목록이라고합니다. 단일 링크 된 목록에는 머리 및 / 또는 꼬리 참조가있을 수 있습니다. 꼬리 참조가있는 이점은 O (1)이되는 getFromBack , addToBack 및 removeFromBack 사례입니다.
┌─────────┬─────────┐ ┌─────────┬─────────┐
HEAD ──▶│ data │"pointer"│──▶│ data │"pointer"│──▶ null
└─────────┴────△────┘ └─────────┴─────────┘
SINGLE │
REFERENCE ────┘
Java의 예제 코드 (단위 테스트 포함) - 머리글 링크가있는 단일 목록
XOR 연결된 목록
XOR 연결 목록 은 메모리 효율적 연결 목록 이라고도합니다. 이중 연결 목록의 또 다른 형태입니다. 이것은 XOR 논리 게이트 및 그 특성에 크게 의존합니다.
이것이 왜 메모리 효율적 연결 목록 (Memory-Efficient Linked List)입니까?
이렇게하면 기존의 이중 링크 된 목록보다 적은 메모리를 사용하기 때문에 이렇게 호출됩니다.
이중 링크 된 목록과 다른가요?
예 , 그렇습니다 .
Doubly-Linked List 는 다음 노드와 이전 노드를 가리키는 두 개의 포인터를 저장합니다. 기본적으로 다시 돌아가려면 back 포인터가 가리키는 주소로 이동합니다. next 포인터로 가리키는 주소로 이동합니다. 그것은 같습니다 :
Memory-Efficient Linked List 또는 XOR Linked List 는 두 개가 아닌 하나의 포인터 만 가지고 있습니다. 이것은 이전 주소 (addr (prev)) XOR (^) 다음 주소 (addr (next))를 저장합니다. 다음 노드로 이동하려면 특정 계산을 수행하고 다음 노드의 주소를 찾으십시오. 이전 노드로 이동하는 경우에도 동일합니다. 그것은 같습니다 :
어떻게 작동합니까?
연결된 목록의 작동 방식을 이해하려면 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 저장 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 ^ 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의해 수행됩니다. 그러면 처음에 새 노드가 삽입됩니다. 이 함수를 호출하면 새 노드를 머리로두고 이전 머리 노드를 두 번째 노드로 놓습니다.Traversal : 이것은
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/
내가 메인에서 내 자신의 대답 에서 많은 내용을 찍은 것을 유의하십시오.
목록 건너 뛰기
건너 뛰기 목록은 올바른 노드로 건너 뛸 수있는 링크 된 목록입니다. 이것은 일반적인 단일 링크드리스트보다 훨씬 빠른 방법입니다. 기본적으로 단일 링크 된 목록 이지만 포인터는 한 노드에서 다음 노드로 이동하지 않지만 소수의 노드는 건너 뜁니다. 따라서 "Skip List"라는 이름.
이것은 단일 링크드리스트와 다른가?
예 , 그렇습니다 .
단일 링크 된 목록은 각 노드가 다음 노드를 가리키는 목록입니다. 단일 연결 목록의 그래픽 표현은 다음과 같습니다.
건너 뛰기 목록은 각 노드가 그 뒤에있을 수도 있고 가지지 않을 수도있는 노드를 가리키는 목록입니다. 건너 뛰기 목록의 그래픽 표현은 다음과 같습니다.
어떻게 작동합니까?
건너 뛰기 목록은 간단합니다. 위 이미지에서 노드 3에 액세스하려고한다고 가정 해 봅시다. 세 번째 노드 이후이므로 머리에서 네 번째 노드로 이동하는 경로는 사용할 수 없습니다. 그래서 우리는 머리에서 두 번째 노드로 이동 한 다음 세 번째 노드로 이동합니다.
그래픽 표현은 다음과 같습니다.
참고 문헌
이중 링크 목록
이중 연결리스트는의 유형 연결리스트 . 이중 연결 목록의 노드에는 다른 노드에 대해 "다음"과 "이전"이라는 두 개의 "포인터"가 있습니다. 각 노드에는 다른 노드에 대한 "포인터"가 두 개 있기 때문에 이중 연결 목록이라고합니다. 이중 링크리스트는 헤드 및 / 또는 테일 포인터를 가질 수있다.
┌─────────┬─────────┬─────────┐ ┌─────────┬─────────┬─────────┐
null ◀──┤previous │ data │ next │◀──┤previous │ data │ next │
│"pointer"│ │"pointer"│──▶│"pointer"│ │"pointer"│──▶ null
└─────────┴─────────┴─────────┘ └─────────┴─────────┴─────────┘
▲ △ △
HEAD │ │ DOUBLE │
└──── REFERENCE ────┘
이중 연결 목록은 단독 연결 목록보다 공간 효율적입니다. 그러나 일부 작업의 경우 시간 효율성이 크게 향상됩니다. 간단한 예제는 get 함수입니다. head 및 tail 참조가있는 이중 링크 목록의 경우 가져올 요소의 인덱스에 따라 head 또는 tail에서 시작합니다. n 요소 목록의 경우, n/2 + i 색인 요소를 얻으려면 머리 / 꼬리 참조가있는 단일 링크 목록이 꼬리에서 "돌아갈"수 없으므로 n/2 + i 노드를 통과해야합니다. 머리 / 꼬리 참조가있는 이중 연결된 목록은 역순으로 목록을 가로 지르는 꼬리에서 "돌아갈"수 있기 때문에 n/2 - i 노드를 탐색하면됩니다.
Java에서 기본 SinglyLinkedList 예제
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();
}
}
}