건너뛰기 목록 Java

스킵 목록 Java는 요소의 하위 시퀀스에 연결되는 연결 목록 계층 구조의 도움으로 정렬된 요소 목록을 저장하는 데 사용되는 데이터 구조입니다. Skip List를 사용하면 항목 조회를 효율적으로 처리할 수 있습니다. 건너뛰기 목록은 확률적 데이터 구조입니다. 즉, 전체 목록에서 여러 요소를 건너뛰므로 건너뛰기 목록이라고 합니다. 건너뛰기 목록을 연결 목록의 확장 버전으로 사용할 수 있습니다. 연결된 목록에서 요소를 삽입, 제거하고 검색하는 방법과 유사하게 건너뛰기 목록에서도 요소를 검색하고 목록에서 요소를 제거하고 요소를 삽입할 수 있습니다. 여기에는 후속 요소의 링크 계층 구조를 유지하는 요소 집합이 포함된 기본 목록이 포함됩니다.

광고 이 카테고리에서 인기 있는 강좌 JAVA MASTERY - 전문 분야 | 78 코스 시리즈 | 15가지 모의고사

무료 소프트웨어 개발 과정 시작

웹 개발, 프로그래밍 언어, 소프트웨어 테스팅 등

구문:

Skip List에는 특별한 구문이 없지만 알고리즘이 있습니다. 알고리즘을 살펴보기 전에 기본적인 Skip List 연산의 종류를 먼저 확인해야 합니다.

• 삽입 작업: Skip list에서는 특정 상황에서 특정 위치에 새 노드를 추가하는 데 사용됩니다
• 검색 작업: Skip 목록에서 특정 노드를 검색하는 데 사용됩니다
• 삭제 작업: Skip 목록에서는 특정 상황에서 노드를 삭제하는 데 사용됩니다

Java에서 건너뛰기 목록 작업

그럼 건너뛰기 목록이 실제로 알고리즘 방식으로 어떻게 작동하는지 살펴보겠습니다.

삽입 알고리즘

1단계: 목록의 각 요소가 노드로 표시되고 노드의 수준은 목록에 삽입될 때 무작위로 선택되므로 노드 수준 결정

2단계: 아래 단계에 따라 노드의 레벨이 결정됩니다

3단계: L(N) = logp/2N에 의해 ​​결정되는 건너뛰기 목록의 수준 수에 대한 상한이 되는 최대 수준을 찾습니다. 이렇게 하면 무작위 레벨이 최대 레벨보다 높아집니다

4단계: 최상위 레벨부터 삽입이 시작되어 현재 노드의 다음 노드를 비교합니다

5단계: 다음 노드 키가 삽입된 키보다 작으면 동일한 수준으로 앞으로 나아갈 수 있습니다

6단계: 다음 노드 키가 삽입된 키보다 크면 현재 노드 I에 대한 포인터를 저장하고 한 수준 아래로 이동하여 검색을 계속해야 합니다.

검색 알고리즘

1단계: 요소 검색은 건너뛰기 목록에서 요소를 삽입할 지점을 검색하는 것과 매우 유사합니다.

2단계: 다음 노드 키가 검색 키보다 작으면 동일한 수준으로 이동할 수 있습니다

3단계: 다음 노드 키가 삽입된 키보다 크면 현재 노드 I에 대한 포인터를 저장하고 한 수준 아래로 이동하여 검색을 계속해야 합니다.

4단계: 가장 낮은 수준에서 가장 오른쪽 요소의 다음 요소에 검색 키와 동일한 키가 있으면 키를 찾은 것입니다. 그렇지 않으면 실패입니다.

삭제 알고리즘

1단계: k와 같은 요소를 삭제하려면 먼저 검색 알고리즘을 사용하여 건너뛰기 목록에서 해당 요소를 찾아야 합니다.

2단계: 검색 알고리즘을 사용하여 요소를 찾은 후에는 단일 연결 목록에서와 마찬가지로 목록에서 요소를 제거하기 위해 포인터 재배열이 수행됩니다.

3단계: 건너뛰기 목록의 가장 낮은 수준부터 시작하여 I not 요소 k 옆에 요소를 재정렬해야 합니다.

4단계: 요소 삭제 후 레벨에 요소가 없는 상황이 발생할 수 있으므로 건너뛰기 목록 레벨을 줄여 이러한 레벨을 제거해야 합니다.

Java의 건너뛰기 목록 예시

코드:

import java.util.Iterator;
import java.util.Random;
import java.util.NoSuchElementException;
public class SkipListJava<K extends Comparable<K>, V> implements Iterable<K> {
private int listsize;
private double pb;
protected static final Random randomGen = new Random();
protected static final double DEFAULT_PB = 0.5;
private NodeKeyValue<K, V> head;
public SkipListJava() {
this(DEFAULT_PB);
}
public SkipListJava(double pb) {
this.head = new NodeKeyValue<K, V>(null, null, 0);
this.pb = pb;
this.listsize = 0;
}
public V get(K key) {
checkKeyValid(key);
NodeKeyValue<K, V> listnode = findNode(key);
if (listnode.getKey().compareTo(key) == 0)
return listnode.getValue();
else
return null;
}
public void add(K key, V value) {
checkKeyValid(key);
NodeKeyValue<K, V> listnode = findNode(key);
if (listnode.getKey() != null && listnode.getKey().compareTo(key) == 0) {
listnode.setValue(value);
return;
}
NodeKeyValue<K, V> newlistNode = new NodeKeyValue<K, V>(key, value, listnode.getLevel());
horizontalInsertList(listnode, newlistNode);
int curLevel = listnode.getLevel();
int headlistLevel = head.getLevel();
while (isBuildLevel()) {
if (curLevel >= headlistLevel) {
NodeKeyValue<K, V> newHeadEle = new NodeKeyValue<K, V>(null, null, headlistLevel + 1);
verticalLink(newHeadEle, head);
head = newHeadEle;
headlistLevel = head.getLevel();
}
while (listnode.getUp() == null) {
listnode = listnode.getPrevious();
}
listnode = listnode.getUp();
NodeKeyValue<K, V> tmp = new NodeKeyValue<K, V>(key, value, listnode.getLevel());
horizontalInsertList(listnode, tmp);
verticalLink(tmp, newlistNode);
newlistNode = tmp;
curLevel++;
}
listsize++;
}
public void remove(K key) {
checkKeyValid(key);
NodeKeyValue<K, V> listnode = findNode(key);
if (listnode == null || listnode.getKey().compareTo(key) != 0)
throw new NoSuchElementException("Key does not exist!");
while (listnode.getDownList() != null)
listnode = listnode.getDownList();
NodeKeyValue<K, V> previous = null;
NodeKeyValue<K, V> next = null;
for (; listnode != null; listnode = listnode.getUp()) {
previous = listnode.getPrevious();
next = listnode.getNext();
if (previous != null)
previous.setNext(next);
if (next != null)
next.setPreviousVal(previous);
}
while (head.getNext() == null && head.getDownList() != null) {
head = head.getDownList();
head.setUp(null);
}
listsize--;
}
public boolean contains(K key) {
return get(key) != null;
}
public int listsize() {
return listsize;
}
public boolean empty() {
return listsize == 0;
}
protected NodeKeyValue<K, V> findNode(K key) {
NodeKeyValue<K, V> listnode = head;
NodeKeyValue<K, V> next = null;
NodeKeyValue<K, V> down = null;
K nodeKey = null;
while (true) {
next = listnode.getNext();
while (next != null && lessThanEqual(next.getKey(), key)) {
listnode = next;
next = listnode.getNext();
}
nodeKey = listnode.getKey();
if (nodeKey != null && nodeKey.compareTo(key) == 0)
break;
down = listnode.getDownList();
if (down != null) {
listnode = down;
} else {
break;
}
}
return listnode;
}
protected void checkKeyValid(K key) {
if (key == null)
throw new IllegalArgumentException("Key must be not null!");
}
protected boolean lessThanEqual(K a, K b) {
return a.compareTo(b) <= 0;
}
protected boolean isBuildLevel() {
return randomGen.nextDouble() < pb;
}
protected void horizontalInsertList(NodeKeyValue<K, V> a, NodeKeyValue<K, V> b) {
b.setPreviousVal(a);
b.setNext(a.getNext());
if (a.getNext() != null)
a.getNext().setPreviousVal(b);
a.setNext(b);
}
protected void verticalLink(NodeKeyValue<K, V> a, NodeKeyValue<K, V> b) {
a.setDown(b);
b.setUp(a);
}
@Override
public String toString() {
StringBuilder stringbuild = new StringBuilder();
NodeKeyValue<K, V> listnode = head;
while (listnode.getDownList() != null)
listnode = listnode.getDownList();
while (listnode.getPrevious() != null)
listnode = listnode.getPrevious();
if (listnode.getNext() != null)
listnode = listnode.getNext();
while (listnode != null) {
stringbuild.append(listnode.toString()).append("\n");
listnode = listnode.getNext();
}
return stringbuild.toString();
}
@Override
public Iterator<K> iterator() {
return new SkipListIterator<K, V>(head);
}
protected static class SkipListIterator<K extends Comparable<K>, V> implements Iterator<K> {
private NodeKeyValue<K, V> listnode;
public SkipListIterator(NodeKeyValue<K, V> listnode) {
while (listnode.getDownList() != null)
listnode = listnode.getDownList();
while (listnode.getPrevious() != null)
listnode = listnode.getPrevious();
if (listnode.getNext() != null)
listnode = listnode.getNext();
this.listnode = listnode;
}
@Override
public boolean hasNext() {
return this.listnode != null;
}
@Override
public K next() {
K result = listnode.getKey();
listnode = listnode.getNext();
return result;
}
@Override
public void remove() {
throw new UnsupportedOperationException();
}
}
protected static class NodeKeyValue<K extends Comparable<K>, V> {
private K key;
private V value;
private int skiplevel;
private NodeKeyValue<K, V> up, down, next, previous;
public NodeKeyValue(K key, V value, int skiplevel) {
this.key = key;
this.value = value;
this.skiplevel = skiplevel;
}
@Override
public String toString() {
StringBuilder stringbuild = new StringBuilder();
stringbuild.append("Node[")
.append("key:");
if (this.key == null)
stringbuild.append("None");
else
stringbuild.append(this.key.toString());
stringbuild.append(", value:");
if (this.value == null)
stringbuild.append("None");
else
stringbuild.append(this.value.toString());
stringbuild.append("]");
return stringbuild.toString();
}
public K getKey() {
return key;
}
public void setKey(K key) {
this.key = key;
}
public V getValue() {
return value;
}
public void setValue(V value) {
this.value = value;
}
public int getLevel() {
return skiplevel;
}
public void setLevel(int skiplevel) {
this.skiplevel = skiplevel;
}
public NodeKeyValue<K, V> getUp() {
return up;
}
public void setUp(NodeKeyValue<K, V> up) {
this.up = up;
}
public NodeKeyValue<K, V> getDownList() {
return down;
}
public void setDown(NodeKeyValue<K, V> down) {
this.down = down;
}
public NodeKeyValue<K, V> getNext() {
return next;
}
public void setNext(NodeKeyValue<K, V> next) {
this.next = next;
}
public NodeKeyValue<K, V> getPrevious() {
return previous;
}
public void setPreviousVal(NodeKeyValue<K, V> previous) {
this.previous = previous;
}
}
public static void main(String[] args) {
SkipListJava<Integer, String> skip = new SkipListJava<>();
for (int i = 20; i < 35; i++) {
skip.add(i, String.valueOf(i));
}
System.out.println(skip);
assert skip.listsize() == 10;
int count = 0;
for (Integer i : skip)
assert i.equals(count++);
skip.remove(23);
System.out.println(skip);
skip.remove(25);
skip.remove(33);
skip.remove(30);
System.out.println(skip);
skip.remove(28);
skip.add(25, "25");
System.out.println(skip);
assert skip.listsize() == 0;
assert skip.empty();
}
}

출력:

스킵 목록에 추가, 스킵 목록에서 검색, 스킵 목록에서 제거를 위해 이 코드를 작성했습니다.

결론

이것으로 '스킵 리스트 자바' 주제를 마치겠습니다. 우리는 건너뛰기 목록 Java가 무엇인지, 그리고 건너뛰기 목록에서 요소 검색, 삽입 및 삭제/제거를 위한 알고리즘과 어떻게 작동하는지 살펴보았습니다. 또한 건너뛰기 목록의 모든 작업을 한 번에 수행하는 좋은 예가 있습니다. 마음속에 떠오르는 아주 다른 예나 논리를 사용해 볼 수도 있습니다. Skip list의 개념은 데이터 구조의 주요 알고리즘 중 하나인 모든 프로그래밍 언어에서 동일합니다.

위 내용은 건너뛰기 목록 Java의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!