データ構造:1～3双方向接続リスト

今回の投稿では、まずすべてのソースコードを公開し、機能単位で説明します.

public class DoubleLinkedList {
	DNode head = null;
	DNode tail = null;
	int size = 0;
	
	DNode findNode(int index) {
		//1. 인덱스 음수고, 사이즈보다 크거나 같으면 예외 발생
		if (index < 0 || index >= size) {
			throw new ArrayIndexOutOfBoundsException();
		}
		
		DNode pointer;
		int flag = 0;
		
		if (size/2 > index) {
			//2. 앞에서 찾기
			pointer = head;
			flag = 0;
			while (flag != index) {
				pointer = pointer.right;
				++flag;
			}
		} else {
			//3. 뒤에서 찾기
			pointer = tail;
			flag = size-1;
			while (flag != index) {
				pointer = pointer.left;
				--flag;
			}
		}
		return pointer;
	}
	
	Object getData(int index) {
		return this.findNode(index).data;
	}
	
	boolean isEmpty() {
		return size == 0;
	}
	
	int size() {
		return size;
	}
	
	void addLast(Object data) {
		this.add(size, data);
	}
	
	void addFirst(Object data) {
		this.add(0, data);
	}
	
	void removeFirst() {
		this.remove(0);
	}
	
	void removeLast() {
		this.remove(size-1);
	}
	
	void add(int index, Object data) {
		DNode newNode = new DNode();
		newNode.data = data;
		if (index == 0 || size == index) {
			//1. 최초 노드 삽입 or 맨앞 or 맨 뒤에 노드 삽입 시
			// 최초 -> index == 0, size == index
			// 맨앞 -> index == 0
			// 맨뒤 -> size==index
			if (this.head == null && this.tail == null) {
				this.head = newNode;
				this.tail = newNode;
			} else if (index == 0) {
				newNode.right = this.head;
				this.head.left = newNode;
				this.head = newNode;
			} else {
				newNode.left = this.tail;
				this.tail.right = newNode;
				this.tail = newNode;
			}
		} else {
			//2. 특정 인덱스에 데이터를 삽입하는 경우	
			DNode foundNode = this.findNode(index);
			DNode leftNode = foundNode.left;
			//새로운 노드와 찾은 노드의 연결
			newNode.right = foundNode;
			foundNode.left = newNode;
			//새로운 노드와 왼쪽 노드의 연결
			newNode.left = leftNode;
			leftNode.right = newNode;
		}
		++size;
	}
	
	void remove(int index) {
		DNode foundNode = this.findNode(index);
		DNode leftNode = foundNode.left;
		DNode rightNode = foundNode.right;
		
		if (leftNode != null) {
			leftNode.right = rightNode;
		} 
		if (rightNode != null) {
			rightNode.left = leftNode;
		}
		if (index == 0) {
			this.head = rightNode;
		}
		if (index == size-1) {
			this.tail = leftNode;
		}
		
		foundNode.left = null;
		foundNode.right = null;
		foundNode.data = null;
		
		--size;
	}
	
    @Override
    public String toString() {
        StringBuilder stringBuilder = new StringBuilder();
        DNode pointer = head;
        stringBuilder.append("head").append(" -> ");
        while (null != pointer) {
            stringBuilder.append(pointer.data).append(" -> ");
            pointer = pointer.right;
        }
        stringBuilder.append("null ");
        if (null != tail) {
            stringBuilder.append(", tail(").append(tail.data).append("), ");
        }
        pointer = tail;
        stringBuilder.append("tail").append(" -> ");
        while (null != pointer) {
            stringBuilder.append(pointer.data).append(" -> ");
            pointer = pointer.left;
        }
        stringBuilder.append("null");
        if (null != head) {
            stringBuilder.append(", head(").append(head.data).append(")");
        }
        return stringBuilder.toString();
    }
}

実装コードは、一方向接続リストよりも複雑である可能性があります.しかし,ノード配置の変化を考慮し,原理を理解すれば実現は難しくないはずである.
今日必要な関数は以下の通りです.

()関数

を挿入

()関数の削除
->挿入と削除は場所によって異なります.

ナビゲーション()関数
->この探索を導入しなければならない.

1.関数の挿入()

挿入方式は、最初の挿入、一番前の挿入、最後の挿入、中間の挿入に分けられます.すなわち,4つの論理に対応できる論理を記述する.


-初期挿入時
初期にはheadとtailはnull値に設定されていたはずです.また、接続リストのsizeも0です.新しいノードが作成されると、headとtailは新しいノードのアドレス値を格納することができます.
-一番前に挿入する場合
既存のノードのアドレスを、新しく作成したノードの右側の領域に格納します.次に、新しく作成したノードのアドレスを既存のノードの左側の領域に格納すればよい.最後にheadを新しいノードのアドレス値に更新すればよい.
-最後の挿入時
既存のノードのアドレスを、新しく作成したノードの左側の領域に格納します.次に、新しく作成したノードのアドレスを既存のノードの右側の領域に格納します.最後にtailを新しく生成したノードのアドレス値に更新すればよい.
-挿入時
新しいノードの左と右は、両方のノードのアドレス値で入力されます.また,左側ノードの右側は新しいノードのアドレス値,右側ノードの左側は新しいノードのアドレス値である.
実装コードは以下の通りです.

	void add(int index, Object data) {
		DNode newNode = new DNode();
		newNode.data = data;
		if (index == 0 || size == index) {
			//1. 최초 노드 삽입 or 맨앞 or 맨 뒤에 노드 삽입 시
			// 최초 -> index == 0, size == index
			// 맨앞 -> index == 0
			// 맨뒤 -> size==index
			if (this.head == null && this.tail == null) {
				this.head = newNode;
				this.tail = newNode;
			} else if (index == 0) {
				newNode.right = this.head;
				this.head.left = newNode;
				this.head = newNode;
			} else {
				newNode.left = this.tail;
				this.tail.right = newNode;
				this.tail = newNode;
			}
		} else {
			//2. (중간삽입)특정 인덱스에 데이터를 삽입하는 경우	
			DNode foundNode = this.findNode(index);
			DNode leftNode = foundNode.left;
			//새로운 노드와 찾은 노드의 연결
			newNode.right = foundNode;
			foundNode.left = newNode;
			//새로운 노드와 왼쪽 노드의 연결
			newNode.left = leftNode;
			leftNode.right = newNode;
		}
		++size;
	}

2.()関数の削除

ノードの削除にも4つの方法があります.
ノードが1つ残っている場合は、削除方法、一番前のノードの削除、一番後ろのノードの削除、真ん中のノードの削除に分けます.1つの関数では,各方式に対応する論理を記述すべきである.


-ノードが1つしか残っていない場合は削除
最も単純です.headとtailをnullに初期化するだけです.削除するノードはゴミ収集器で収集されます.
-一番前のノードを削除
削除するノードの次のノードの左側の領域をnullに初期化します.次に、headを削除するノードの次のノードのアドレスに更新します.次に、削除するノードの左側、data、右側の領域をnullに初期化します.
-最後のノードを削除
削除するノードの前のノードの右側の領域をnullに初期化します.次にtailを削除するノードの前のノードのアドレス値に更新します.最後に、削除するノードの左、データ、右の領域をすべてnullに初期化します.
-中間ノードを削除
削除するノードの前のノードの右側の領域を、削除するノードの次のノードのアドレス値に置き換えます.同様に、削除するノードの後続ノードの左側の領域は、削除するノードの前のノードのアドレス値に置き換えられます.ノードを削除するデータ、左、右の領域をnullで置き換えます.
以上の4つの方式は、多様な条件の制御ゲートを用いて処理しなければならない.

	void remove(int index) {
		DNode foundNode = this.findNode(index);
		DNode leftNode = foundNode.left;
		DNode rightNode = foundNode.right;
		
       
		if (leftNode != null) {
        	//scope 1. 좌측 노드가 존재할 경우
			leftNode.right = rightNode;
		} 
		if (rightNode != null) {
        	//scope 2. 우측 노드가 존재할 경우
			rightNode.left = leftNode;
		}
		if (index == 0) {
        	//scope 3. 첫번째 노드를 삭제할 경우
			this.head = rightNode;
		}
		if (index == size-1) {
        	//scope 4. 마지막 노드를 삭제할 경우
			this.tail = leftNode;
		}
		
		foundNode.left = null;
		foundNode.right = null;
		foundNode.data = null;
		
		--size;
	}

あ….これはいったい何ですか.🐶声かどうか聞いてもいいです
いくつかの例を挙げて説明します
最初のノード

を削除するときは

である.

scope 2、3動作

要素が1つしか残っていない場合は、

を削除します.

scope 3、4動作

中間ノードを削除する場合は

である.

scope 1,2動作

最後のノード

を削除すると

となる.

scope 1,4動作

3.ナビゲーション()関数

双方向接続リストにtailという新しい友達が表示されます.検索するインデックスが中間値より小さい場合はheadから検索を開始し、中間値より大きい場合はtailから検索を開始します.すなわち,この関数は二分探索だけで簡単に実現できる.

入力条件文の値は、ポインタに割り当てられた値に依存します.ヘッドから出発して、右に1格移動して、私たちが探している要素を持ってきてくれればいいのに.tailから出発して、左に1つ移動して、私たちが探している要素を持ってきてください.

	DNode findNode(int index) {
		//1. 인덱스 음수고, 사이즈보다 크거나 같으면 예외 발생
		if (index < 0 || index >= size) {
			throw new ArrayIndexOutOfBoundsException();
		}
		
		DNode pointer;
		int flag = 0;
		
		if (size/2 > index) {
			//2. 앞에서 찾기
			pointer = head;
			flag = 0;
			while (flag != index) {
				pointer = pointer.right;
				++flag;
			}
		} else {
			//3. 뒤에서 찾기
			pointer = tail;
			flag = size-1;
			while (flag != index) {
				pointer = pointer.left;
				--flag;
			}
		}
		return pointer;
	}

4.整理

こうして双方向接続リストの実装を終了するノードがどのように変化し,左−右領域の値が何であるかを理解すれば,双方向を遠慮なく理解できる.次の章はStackです.