스킵 목록 Java는 요소의 하위 시퀀스에 연결되는 연결 목록 계층 구조의 도움으로 정렬된 요소 목록을 저장하는 데 사용되는 데이터 구조입니다. Skip List를 사용하면 항목 조회를 효율적으로 처리할 수 있습니다. 건너뛰기 목록은 확률적 데이터 구조입니다. 즉, 전체 목록에서 여러 요소를 건너뛰므로 건너뛰기 목록이라고 합니다. 건너뛰기 목록을 연결 목록의 확장 버전으로 사용할 수 있습니다. 연결된 목록에서 요소를 삽입, 제거하고 검색하는 방법과 유사하게 건너뛰기 목록에서도 요소를 검색하고 목록에서 요소를 제거하고 요소를 삽입할 수 있습니다. 여기에는 후속 요소의 링크 계층 구조를 유지하는 요소 집합이 포함된 기본 목록이 포함됩니다.
광고 이 카테고리에서 인기 있는 강좌 JAVA MASTERY - 전문 분야 | 78 코스 시리즈 | 15가지 모의고사무료 소프트웨어 개발 과정 시작
웹 개발, 프로그래밍 언어, 소프트웨어 테스팅 등
구문:
Skip List에는 특별한 구문이 없지만 알고리즘이 있습니다. 알고리즘을 살펴보기 전에 기본적인 Skip List 연산의 종류를 먼저 확인해야 합니다.
그럼 건너뛰기 목록이 실제로 알고리즘 방식으로 어떻게 작동하는지 살펴보겠습니다.
1단계: 목록의 각 요소가 노드로 표시되고 노드의 수준은 목록에 삽입될 때 무작위로 선택되므로 노드 수준 결정
2단계: 아래 단계에 따라 노드의 레벨이 결정됩니다
3단계: L(N) = logp/2N에 의해 결정되는 건너뛰기 목록의 수준 수에 대한 상한이 되는 최대 수준을 찾습니다. 이렇게 하면 무작위 레벨이 최대 레벨보다 높아집니다
4단계: 최상위 레벨부터 삽입이 시작되어 현재 노드의 다음 노드를 비교합니다
5단계: 다음 노드 키가 삽입된 키보다 작으면 동일한 수준으로 앞으로 나아갈 수 있습니다
6단계: 다음 노드 키가 삽입된 키보다 크면 현재 노드 I에 대한 포인터를 저장하고 한 수준 아래로 이동하여 검색을 계속해야 합니다.
1단계: 요소 검색은 건너뛰기 목록에서 요소를 삽입할 지점을 검색하는 것과 매우 유사합니다.
2단계: 다음 노드 키가 검색 키보다 작으면 동일한 수준으로 이동할 수 있습니다
3단계: 다음 노드 키가 삽입된 키보다 크면 현재 노드 I에 대한 포인터를 저장하고 한 수준 아래로 이동하여 검색을 계속해야 합니다.
4단계: 가장 낮은 수준에서 가장 오른쪽 요소의 다음 요소에 검색 키와 동일한 키가 있으면 키를 찾은 것입니다. 그렇지 않으면 실패입니다.
1단계: k와 같은 요소를 삭제하려면 먼저 검색 알고리즘을 사용하여 건너뛰기 목록에서 해당 요소를 찾아야 합니다.
2단계: 검색 알고리즘을 사용하여 요소를 찾은 후에는 단일 연결 목록에서와 마찬가지로 목록에서 요소를 제거하기 위해 포인터 재배열이 수행됩니다.
3단계: 건너뛰기 목록의 가장 낮은 수준부터 시작하여 I not 요소 k 옆에 요소를 재정렬해야 합니다.
4단계: 요소 삭제 후 레벨에 요소가 없는 상황이 발생할 수 있으므로 건너뛰기 목록 레벨을 줄여 이러한 레벨을 제거해야 합니다.
코드:
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 중국어 웹사이트의 기타 관련 기사를 참조하세요!