LinkedListとaddFirstメソッド

LinkedList

LinkedListバー

ポインタを使用して複数のノードを接続するデータ構造を接続リストと呼びます.
ノードには2つの構成があります.
1番目は隣接するノードを指すnextというポインタで、2番目はノードに入れるデータを指します.(ノードDについては、後ろに何もないのでnullを指す)
このリストはheadというポインタから始まります.Headはリストの最初のノードを指します.お尻ではこの接続リストのheadしか知らないnextまたはhead.ノードの内容(データなど)を検索します.ただし、接続リストの長さが長い場合は、headの後にnextを追加することはできません.そこで,一時ポインタを用いてナビゲーションを行った.

アレイとの相違

配列には、複数のデータを順番に格納する共通点もあります.ただし、配列のサイズが大きすぎたり、小さすぎたりする可能性があるので、配列のサイズを再調整する必要があります.
配列とは異なり、接続リストの設計は常に正しいサイズを維持します.したがって、連続データや大量のデータがある場合によく使用されます.

ノードとサイズ

次のコードはLinkedListの内部クラスでノードを定義している.

public class LinkedList <E> implements ListI<E>{
	// 노드 정의
	class Node<E>{
		E data;
		Node<E> next;
		public Node(E obj){
			data=obj;
			next=null;
		}
	}
	private Node<E> head;

	private int currentSize;
	
	public LinkedList(){
		head=null;
		currentsize=null;
	}
}

Genericを使用するノードクラスには、次のものがあります.
dataというポインタとnextというノードを定義した後、ノードオブジェクトを完了するためにコンストラクション関数を追加しました.
ジェネレータの作成時にJENICは使用しません.
作成者はオブジェクトをデータに格納し、nextはまずnullとして指定します.このノードオブジェクトは、外部からアクセスできない内部クラスである必要があります.
これは、ノードが外部からアクセスすると、位置が変化し、最終的に情報が失われるためです.
外部からアクセスするには、ノードオブジェクトを作成するときに示すようにprivate変数headを作成します.

ノード数を計算する有効な方法

intタイプの変数currentSizeを作成して、ノードの数を直接計算するよりも効率的に計算します.
currentSizeを作成し、要素をリストに追加すると、currentSizeの値を大きくすることで、リストのサイズをすぐに知ることができます.

きょうかいじょうけん

接続リストを使用する際に考慮すべき条件を見てみましょう.
この境界条件は、任意のデータ構造を考慮する必要があります.

1. 자료 구조가 비어있는 경우
2. 자료 구조에 단 하나의 요소가 들어있을 때
3. 자료 구조의 첫 번째 요소를 제거하거나 추가할 때
4. 자료 구조의 마지막 요소를 제거하거나 추가할 때
5. 자료 구조의 중간 부분을 처리할 때

addFirstメソッド

addFirstメソッドを使用して、接続リストの前にノードを追加できます.

1. 새로운 node를 만든다.
2. 새로운 node의 next가 현재 head를 가리키도록 한다.
3. head 포인터가 다시 새로운 노드를 가리키도록 한다.

headがnullの接続リストに新しい要素を追加することを考えてみましょう.
まずnextとdataを持つノードクラスオブジェクトを作成し、接続リストが空の場合headがインポートされ、新しく作成したheadは新しく作成したノードを指します.
次の図に示します.

次に、リストの一番前に別のノードを追加します.
新しいノードがあれば、headは新しいノードを指摘しますか?
そうなると、Aを指摘する人がいないとGCが発生します.

前述したように、上図に示すような状況は発生してはならないので、新しいノードが発生した場合、新しいノードのnextもAであることを示すべきである.
そしてやっと頭を動かすことができました

結果headはBを指しAを指す
前に要素を追加しながら、接続リストのサイズを大きくすることができます.
このタスクの時間的複雑さは1です.
この内容をコードとして記述します.

   public void addFirst(E obj){
	Node<E> node = new Node<E>(obj); // 1 새로운 노드생성
	node.next = head; // 2 위 그림에서 파란선
	head = node; // 3 위 그림에서 빨간선 
}