片端リンク リストおよび両端リンク リスト データ構造の Java シミュレーションの例
- 高洛峰オリジナル
- 2017-01-24 16:05:441497ブラウズ
単一リンク リストをシミュレートする
線形テーブル:
線形テーブル (シーケンス テーブルとも呼ばれる) は、最も基本的で、最も単純で、最も一般的に使用されるデータ構造です。
線形テーブル内のデータ要素間の関係は 1 対 1 の関係です。つまり、最初と最後のデータ要素を除いて、他のデータ要素は端から端まで接続されます。
線形テーブルの論理構造はシンプルで、実装と操作が簡単です。
実際のアプリケーションでは、線形テーブルは、スタック、キュー、文字列などの特別な線形テーブルの形式で使用されます。
線形構造の基本的な特性は次のとおりです。
1.セットには「最初の要素」が 1 つだけ存在する必要があります。
2.セットには「最後の要素」が 1 つだけ存在する必要があります。
3.最後の要素を除いて、すべての要素には一意の後継者 (結果) があります。最初の要素を除いて、すべての要素には固有の前駆体 (先行要素) があります。
リンク リストは、物理ストレージ ユニット上の非連続かつ非順次のストレージ構造です。データ要素の論理的順序は、リンク リスト内のポインターのリンク順序によって実現されます。
各データ項目は次のとおりです。 「チェーン」「ノード」（リンク）に含まれます。
リンクポイントはクラスのオブジェクトであり、Linkと呼ぶことができます。リンク リストには同様のリンク ポイントが多数あり、各リンクには次のリンク ポイントを参照するフィールド next が含まれています。
リンク リスト オブジェクト自体は、最初に最初のリンク ポイントを指す参照を保存します。 (先頭がない場合は配置できません)
リンクリストは配列のように(添え字を使って)データ項目に直接アクセスすることはできませんが、データ間の関係を利用して配置する、つまり次のリンクポイントにアクセスする必要があります。リンク ポイントによって参照され、必要なデータにアクセスするまで次のチェーンに進みます。これは、参照のポインタを変更するだけなので、チェーンの先頭での挿入と削除の時間計算量は O(1) です。そして、挿入後、指定ノードの検索、削除、指定ノードの指定ノードの削除を行うと、平均してリンクリスト内の半分のノードを検索する必要があり、効率はO(N)となります。
単連結リスト:
線形リストを「ノードのシーケンス」として表すことは、線形連結リスト(単連結リスト)と呼ばれます
これは、データ要素を格納するために任意のアドレスを持つ一連の記憶ユニットを使用する、連鎖アクセスのデータ構造です線形リスト内。 (このストレージユニットのグループは連続的または不連続的です)
リンクポイントの構造:
ノード値を格納するデータフィールドデータ(リンクフィールド)。 next
リンク リストは、線形リストの n 個のノードを、各ノードのリンク ドメインを通じて論理的な順序でリンクします。
/**
* 单链表:头插法 后进先出
* 将链表的左边称为链头，右边称为链尾。
* 头插法建单链表是将链表右端看成固定的，链表不断向左延伸而得到的。
* 头插法最先得到的是尾结点
* @author stone
*/
public class SingleLinkedList<T> {
private Link<T> first; //首结点
public SingleLinkedList() {
}
public boolean isEmpty() {
return first == null;
}
public void insertFirst(T data) {// 插入 到 链头
Link<T> newLink = new Link<T>(data);
newLink.next = first; //新结点的next指向上一结点
first = newLink;
}
public Link<T> deleteFirst() {//删除 链头
Link<T> temp = first;
first = first.next; //变更首结点，为下一结点
return temp;
}
public Link<T> find(T t) {
Link<T> find = first;
while (find != null) {
if (!find.data.equals(t)) {
find = find.next;
} else {
break;
}
}
return find;
}
public Link<T> delete(T t) {
if (isEmpty()) {
return null;
} else {
if (first.data.equals(t)) {
Link<T> temp = first;
first = first.next; //变更首结点，为下一结点
return temp;
}
}
Link<T> p = first;
Link<T> q = first;
while (!p.data.equals(t)) {
if (p.next == null) {//表示到链尾还没找到
return null;
} else {
q = p;
p = p.next;
}
}
q.next = p.next;
return p;
}
public void displayList() {//遍历
System.out.println("List (first-->last):");
Link<T> current = first;
while (current != null) {
current.displayLink();
current = current.next;
}
}
public void displayListReverse() {//反序遍历
Link<T> p = first, q = first.next, t;
while (q != null) {//指针反向，遍历的数据顺序向后
t = q.next; //no3
if (p == first) {// 当为原来的头时，头的.next应该置空
p.next = null;
}
q.next = p;// no3 -> no1 pointer reverse
p = q; //start is reverse
q = t; //no3 start
}
//上面循环中的if里，把first.next 置空了, 而当q为null不执行循环时，p就为原来的最且一个数据项，反转后把p赋给first
first = p;
displayList();
}
class Link<T> {//链结点
T data; //数据域
Link<T> next; //后继指针，结点 链域
Link(T data) {
this.data = data;
}
void displayLink() {
System.out.println("the data is " + data.toString());
}
}
public static void main(String[] args) {
SingleLinkedList<Integer> list = new SingleLinkedList<Integer>();
list.insertFirst(33);
list.insertFirst(78);
list.insertFirst(24);
list.insertFirst(22);
list.insertFirst(56);
list.displayList();
list.deleteFirst();
list.displayList();
System.out.println("find:" + list.find(56));
System.out.println("find:" + list.find(33));
System.out.println("delete find:" + list.delete(99));
System.out.println("delete find:" + list.delete(24));
list.displayList();
System.out.println("----reverse----");
list.displayListReverse();
}
}List (first-->last): the data is 56 the data is 22 the data is 24 the data is 78 the data is 33 List (first-->last): the data is 22 the data is 24 the data is 78 the data is 33 find:null find:linked_list.SingleLinkedList$Link@4b71bbc9 delete find:null delete find:linked_list.SingleLinkedList$Link@17dfafd1 List (first-->last): the data is 22 the data is 78 the data is 33 ----reverse---- List (first-->last): the data is 33 the data is 78 the data is 22シングル リンク リスト: 末尾挿入メソッド。 -in-first Out - リンク リストの左端が固定され、リンク リストが右に伸び続ける場合、リンク リストを確立するこの方法は末尾挿入と呼ばれます。
末尾補間メソッドが連結リストを作成するとき、先頭ポインタは固定されるため、末尾ポインタは連結リストの右側に拡張するように設定する必要があります。
末尾補間メソッドは、最初に先頭ノードを取得します。public class SingleLinkedList2<T> {
private Link<T> head; //首结点
public SingleLinkedList2() {
}
public boolean isEmpty() {
return head == null;
}
public void insertLast(T data) {//在链尾 插入
Link<T> newLink = new Link<T>(data);
if (head != null) {
Link<T> nextP = head.next;
if (nextP == null) {
head.next = newLink;
} else {
Link<T> rear = null;
while (nextP != null) {
rear = nextP;
nextP = nextP.next;
}
rear.next = newLink;
}
} else {
head = newLink;
}
}
public Link<T> deleteLast() {//删除 链尾
Link<T> p = head;
Link<T> q = head;
while (p.next != null) {// p的下一个结点不为空，q等于当前的p(即q是上一个，p是下一个) 循环结束时，q等于链尾倒数第二个
q = p;
p = p.next;
}
//delete
q.next = null;
return p;
}
public Link<T> find(T t) {
Link<T> find = head;
while (find != null) {
if (!find.data.equals(t)) {
find = find.next;
} else {
break;
}
}
return find;
}
public Link<T> delete(T t) {
if (isEmpty()) {
return null;
} else {
if (head.data.equals(t)) {
Link<T> temp = head;
head = head.next; //变更首结点，为下一结点
return temp;
}
}
Link<T> p = head;
Link<T> q = head;
while (!p.data.equals(t)) {
if (p.next == null) {//表示到链尾还没找到
return null;
} else {
q = p;
p = p.next;
}
}
q.next = p.next;
return p;
}
public void displayList() {//遍历
System.out.println("List (head-->last):");
Link<T> current = head;
while (current != null) {
current.displayLink();
current = current.next;
}
}
public void displayListReverse() {//反序遍历
Link<T> p = head, q = head.next, t;
while (q != null) {//指针反向，遍历的数据顺序向后
t = q.next; //no3
if (p == head) {// 当为原来的头时，头的.next应该置空
p.next = null;
}
q.next = p;// no3 -> no1 pointer reverse
p = q; //start is reverse
q = t; //no3 start
}
//上面循环中的if里，把head.next 置空了, 而当q为null不执行循环时，p就为原来的最且一个数据项，反转后把p赋给head
head = p;
displayList();
}
class Link<T> {//链结点
T data; //数据域
Link<T> next; //后继指针，结点 链域
Link(T data) {
this.data = data;
}
void displayLink() {
System.out.println("the data is " + data.toString());
}
}
public static void main(String[] args) {
SingleLinkedList2<Integer> list = new SingleLinkedList2<Integer>();
list.insertLast(33);
list.insertLast(78);
list.insertLast(24);
list.insertLast(22);
list.insertLast(56);
list.displayList();
list.deleteLast();
list.displayList();
System.out.println("find:" + list.find(56));
System.out.println("find:" + list.find(33));
System.out.println("delete find:" + list.delete(99));
System.out.println("delete find:" + list.delete(78));
list.displayList();
System.out.println("----reverse----");
list.displayListReverse();
}
}List (head-->last): the data is 33 the data is 78 the data is 24 the data is 22 the data is 56 List (head-->last): the data is 33 the data is 78 the data is 24 the data is 22 find:null find:linked_list.SingleLinkedList2$Link@4b71bbc9 delete find:null delete find:linked_list.SingleLinkedList2$Link@17dfafd1 List (head-->last): the data is 33 the data is 24 the data is 22 ----reverse---- List (head-->last): the data is 22 the data is 24 the data is 33両端リンク リストをシミュレートし、リンク リストを使用してスタックとキューを実装します
両端リンク リスト:
両端リンク リストは、以下に非常に似ています。従来のリンク リストでは、新しい属性、つまり最後のリンク ノードの後方を追加するだけですこの方法では、後方の次を変更するだけで済みます。新しいノード。最後のノードを検索するループは必要ありません
したがって、insertFirst、insertLastがあります
チェーンの先頭を削除する場合、チェーンの終端を削除する場合は、参照点を変更するだけで済みます。最後から 2 番目のノードの次のノードを空にします
それを指す参照がないため、操作を読み取るためにループする必要があります
/**
* 双端链表
* @author stone
*/
public class TwoEndpointList<T> {
private Link<T> head; //首结点
private Link<T> rear; //尾部指针
public TwoEndpointList() {
}
public T peekHead() {
if (head != null) {
return head.data;
}
return null;
}
public boolean isEmpty() {
return head == null;
}
public void insertFirst(T data) {// 插入 到 链头
Link<T> newLink = new Link<T>(data);
newLink.next = head; //新结点的next指向上一结点
head = newLink;
}
public void insertLast(T data) {//在链尾 插入
Link<T> newLink = new Link<T>(data);
if (head == null) {
rear = null;
}
if (rear != null) {
rear.next = newLink;
} else {
head = newLink;
head.next = rear;
}
rear = newLink; //下次插入时，从rear处插入
}
public T deleteHead() {//删除 链头
if (isEmpty()) return null;
Link<T> temp = head;
head = head.next; //变更首结点，为下一结点
if (head == null) {
<span style="white-space:pre"> </span>rear = head;
}
return temp.data;
}
public T find(T t) {
if (isEmpty()) {
return null;
}
Link<T> find = head;
while (find != null) {
if (!find.data.equals(t)) {
find = find.next;
} else {
break;
}
}
if (find == null) {
return null;
}
return find.data;
}
public T delete(T t) {
if (isEmpty()) {
return null;
} else {
if (head.data.equals(t)) {
Link<T> temp = head;
head = head.next; //变更首结点，为下一结点
return temp.data;
}
}
Link<T> p = head;
Link<T> q = head;
while (!p.data.equals(t)) {
if (p.next == null) {//表示到链尾还没找到
return null;
} else {
q = p;
p = p.next;
}
}
q.next = p.next;
return p.data;
}
public void displayList() {//遍历
System.out.println("List (head-->last):");
Link<T> current = head;
while (current != null) {
current.displayLink();
current = current.next;
}
}
public void displayListReverse() {//反序遍历
if (isEmpty()) {
return;
}
Link<T> p = head, q = head.next, t;
while (q != null) {//指针反向，遍历的数据顺序向后
t = q.next; //no3
if (p == head) {// 当为原来的头时，头的.next应该置空
p.next = null;
}
q.next = p;// no3 -> no1 pointer reverse
p = q; //start is reverse
q = t; //no3 start
}
//上面循环中的if里，把head.next 置空了, 而当q为null不执行循环时，p就为原来的最且一个数据项，反转后把p赋给head
head = p;
displayList();
}
class Link<T> {//链结点
T data; //数据域
Link<T> next; //后继指针，结点 链域
Link(T data) {
this.data = data;
}
void displayLink() {
System.out.println("the data is " + data.toString());
}
}
public static void main(String[] args) {
TwoEndpointList<Integer> list = new TwoEndpointList<Integer>();
list.insertLast(1);
list.insertFirst(2);
list.insertLast(3);
list.insertFirst(4);
list.insertLast(5);
list.displayList();
list.deleteHead();
list.displayList();
System.out.println("find:" + list.find(6));
System.out.println("find:" + list.find(3));
System.out.println("delete find:" + list.delete(6));
System.out.println("delete find:" + list.delete(5));
list.displayList();
System.out.println("----reverse----");
list.displayListReverse();
}
}List (head-->last): the data is 4 the data is 2 the data is 1 the data is 3 the data is 5 List (head-->last): the data is 2 the data is 1 the data is 3 the data is 5 find:null find:3 delete find:null delete find:5 List (head-->last): the data is 2 the data is 1 the data is 3 ----reverse---- List (head-->last): the data is 3 the data is 1 the data is 2実装するにはリンク リストを使用しますスタック。これは、前方単一リンク リストを挿入することで実現できます。
このクラスは、ダブルエンド リンク リストを使用して以下を実装します。
public class LinkStack<T> {
private TwoEndpointList<T> datas;
public LinkStack() {
datas = new TwoEndpointList<T>();
}
// 入栈
public void push(T data) {
datas.insertFirst(data);
}
// 出栈
public T pop() {
return datas.deleteHead();
}
// 查看栈顶
public T peek() {
return datas.peekHead();
}
//栈是否为空
public boolean isEmpty() {
return datas.isEmpty();
}
public static void main(String[] args) {
LinkStack<Integer> stack = new LinkStack<Integer>();
for (int i = 0; i < 5; i++) {
stack.push(i);
}
for (int i = 0; i < 5; i++) {
Integer peek = stack.peek();
System.out.println("peek:" + peek);
}
for (int i = 0; i < 6; i++) {
Integer pop = stack.pop();
System.out.println("pop:" + pop);
}
System.out.println("----");
for (int i = 5; i > 0; i--) {
stack.push(i);
}
for (int i = 5; i > 0; i--) {
Integer peek = stack.peek();
System.out.println("peek:" + peek);
}
for (int i = 5; i > 0; i--) {
Integer pop = stack.pop();
System.out.println("pop:" + pop);
}
}
} リンク リストを使用したキューの実装 ダブルエンド リンク リストを使用した実装。リンク リスト:
peek:4 peek:4 peek:4 peek:4 peek:4 pop:4 pop:3 pop:2 pop:1 pop:0 pop:null ---- peek:1 peek:1 peek:1 peek:1 peek:1 pop:1 pop:2 pop:3 pop:4 pop:5Print
public class LinkQueue<T> {
private TwoEndpointList<T> list;
public LinkQueue() {
list = new TwoEndpointList<T>();
}
//插入队尾
public void insert(T data) {
list.insertLast(data);
}
//移除队头
public T remove() {
return list.deleteHead();
}
//查看队头
public T peek() {
return list.peekHead();
}
public boolean isEmpty() {
return list.isEmpty();
}
public static void main(String[] args) {
LinkQueue<Integer> queue = new LinkQueue<Integer>();
for (int i = 1; i < 5; i++) {
queue.insert(i);
}
for (int i = 1; i < 5; i++) {
Integer peek = queue.peek();
System.out.println("peek:" + peek);
}
for (int i = 1; i < 5; i++) {
Integer remove = queue.remove();
System.out.println("remove:" + remove);
}
System.out.println("----");
for (int i = 5; i > 0; i--) {
queue.insert(i);
}
for (int i = 5; i > 0; i--) {
Integer peek = queue.peek();
System.out.println("peek2:" + peek);
}
for (int i = 5; i > 0; i--) {
Integer remove = queue.remove();
System.out.println("remove:" + remove);
}
}
} 片リンク リストおよび両端リンク リスト データ構造の Java シミュレーションのその他の例については、PHP 中国語 Web サイトの関連記事に注目してください。
声明：
この記事の内容はネチズンが自主的に寄稿したものであり、著作権は原著者に帰属します。このサイトは、それに相当する法的責任を負いません。盗作または侵害の疑いのあるコンテンツを見つけた場合は、admin@php.cn までご連絡ください。