Langkau Senarai Java-javaTutorial-php.cn

Skip List Java ialah Struktur Data yang digunakan untuk menyimpan senarai isih unsur dengan bantuan hierarki senarai Terpaut yang bersambung kepada jujukan unsur. Langkau Senarai membolehkan untuk memproses carian item dengan cara yang cekap. Langkau senarai ialah struktur data kebarangkalian, yang bermaksud ia melangkau beberapa elemen dalam keseluruhan senarai dan oleh itu dikenali sebagai senarai Langkau. Kita boleh mengambil senarai langkau sebagai versi lanjutan senarai terpaut. Sama seperti cara senarai Terpaut membenarkan penyisipan, pengalihan keluar dan melakukan carian untuk elemen, senarai Langkau juga membenarkan untuk mencari elemen, mengalih keluar elemen daripada senarai dan memasukkan elemen. Ia akan mengandungi senarai asas yang termasuk satu set elemen yang akan mengekalkan hierarki pautan elemen seterusnya.

IKLAN Kursus Popular dalam kategori ini JAVA MASTERY - Pengkhususan | 78 Siri Kursus | 15 Ujian Olok-olok

Mulakan Kursus Pembangunan Perisian Percuma Anda

Pembangunan web, bahasa pengaturcaraan, ujian perisian & lain-lain

Sintaks:

Skip List tidak mempunyai sintaks tertentu, tetapi ia mempunyai Algoritma. Sebelum melihat Algoritma, kita perlu menyemak Jenis Operasi Senarai Langkau Asas.

Operasi Sisipan: Dalam senarai Langkau, ia digunakan untuk menambah nod baharu pada lokasi tertentu dalam situasi tertentu
Operasi Carian: Dalam senarai Langkau, ia digunakan untuk mencari nod tertentu
Operasi Pemadaman: Dalam senarai Langkau, ia digunakan untuk memadamkan nod dalam situasi tertentu

Kerja Senarai Langkau di Java

Jadi mari kita lihat Bagaimana Senarai Langkau sebenarnya berfungsi dengan cara Algoritma.

Algoritma Sisipan

Langkah 1: Menentukan tahap nod kerana setiap elemen dalam senarai diwakili oleh nod dan tahap nod dipilih secara rawak pada masa sisipan dalam senarai

Langkah 2: Tahap untuk nod ditentukan berdasarkan langkah di bawah

Langkah 3: Cari Tahap Maks untuk menjadi sempadan atas pada kiraan tahap dalam senarai langkau, yang ditentukan oleh L(N) = logp/2N. Ini memastikan tahap rawak akan lebih besar daripada Tahap Maks

Langkah 4: Sisipan bermula dari tahap tertinggi dan membandingkan nod seterusnya nod semasa

Langkah 5: Jika kunci nod Seterusnya kurang daripada kunci yang dimasukkan, maka kita boleh bergerak ke hadapan dengan tahap yang sama

Langkah 6: Jika kunci nod seterusnya lebih besar daripada kunci yang dimasukkan, maka kita perlu menyimpan penunjuk ke nod semasa I dan bergerak satu tahap ke bawah meneruskan carian.

Algoritma Carian

Langkah 1: Memandangkan elemen carian sangat serupa dengan mencari tempat untuk memasukkan elemen dalam senarai Langkau.

Langkah 2: Jika kunci nod seterusnya kurang daripada kunci carian, maka kita boleh bergerak ke hadapan pada tahap yang sama

Langkah 3: Jika kunci nod seterusnya lebih besar daripada kunci yang dimasukkan, maka kita perlu menyimpan penunjuk ke nod semasa I dan bergerak satu tahap ke bawah meneruskan carian.

Langkah 4: Pada tahap paling rendah, jika elemen seterusnya ke elemen paling kanan mempunyai kunci yang sama dengan kunci carian, maka kami telah menemui kunci itu jika tidak ia gagal.

Algoritma Pemadaman

Langkah 1: Untuk memadam sebarang elemen, sebut k, mula-mula kita perlu mencari elemen dalam senarai Langkau menggunakan Algoritma Carian.

Langkah 2: Setelah kami menemui elemen menggunakan Algoritma Carian, penyusunan semula penunjuk dilakukan untuk mengalih keluar elemen daripada senarai seperti yang kami lakukan dalam senarai terpaut Tunggal.

Langkah 3: Kita perlu bermula dari peringkat terendah senarai langkau dan susun semula elemen di sebelah I bukan elemen k.

Langkah 4: Selepas pemadaman unsur, mungkin terdapat situasi di mana tahap tanpa unsur, Jadi kita perlu mengalih keluar tahap ini dengan mengurangkan tahap senarai Langkau.

Contoh Senarai Langkau dalam Java

Kod:

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();
}
}

Salin selepas log masuk

Output:

Langkau Senarai Java

Kami telah menulis kod ini untuk menambah senarai langkau, mencari dalam senarai langkau dan mengalih keluar daripada senarai langkau.

Kesimpulan

Dengan ini, kami akan menyimpulkan topik ini 'Langkau Senarai Java'. Kami telah melihat apa itu Langkau senarai Java dan cara ia berfungsi dengan Algoritma untuk Carian, Sisipkan dan Padam/Alih Keluar Elemen daripada senarai Langkau. Juga, dapatkan contoh yang baik yang mempunyai semua operasi senarai langkau sekali gus. Anda masih boleh mencuba dengan contoh atau logik lain yang mungkin anda fikirkan. Konsep Langkau senarai adalah sama dalam mana-mana bahasa pengaturcaraan, salah satu Algoritma utama dalam Struktur Data.

Atas ialah kandungan terperinci Langkau Senarai Java. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!