LinkedList

今日では、すべての資料構造のベースリンクリストで、単一のリンクリストを理解し、コードで直接実装します.

単一リンクリストの概念

上の画像はSingleLinkedListと言えます.図に示すように、各ノードはdata万個だけでなく、reference field、すなわち次のノードへの情報も有する.
上記のノードを簡単に記述すると、次のように記述できます.

class Node {
	let data = Int
	var next = Node?
	init(data: Int, next: Node? = nil) {
	    self.data = data
            self.next = next
	}
}

配列とは異なり、単一チェーンテーブルのランダム要素には定数時間でアクセスできません.すなわち、th番目の要素にアクセスするには、headノードから次のノードから順にアクセスする必要があります.したがって、link−listの長さがNである場合、indexを介してelementにアクセスする平均時間の複雑さはO(N)である.
上の図に示すように、headノードは23になり、3番目の要素にアクセスするには、headノードを使用して2番目のノードのnextノードを指すしかなく、3番目のノードの6を指すnextノードを使用して3番目の要素にアクセスすることもできます.
ここで,配列がindexを介してアクセスするにはO(1)の時間的複雑さが必要であるのに,なぜO(N)の時間的複雑度の低いlinklistを使用しなければならないのか.という疑問もあります.この点については、次のinsertおよびdelete演算について説明することができる.

Add Operation

link-listにprevを追加し、新しい要素を追加する場合は、次の手順に従います.
1.新たに追加されたノードcurノードのデータ値を初期化する.

2.curノードのnextをprevが指すnextに向ける.

3.prevノードのnextをcurに変更する.

アレイ内の要素間に新しい要素を追加する場合は、その要素を挿入し、後続の要素をすべて1つ移動する必要があります.このコストは平均O(N)の時間的複雑さを必要とします.
逆に、link-listはエレメント間に新しいエレメントを挿入し、リンクを変更するだけで済むため、O(1)の時間的複雑さがあります.
また、最初の図を例にとると、以下のようになります.

ここで、6と15の間に新しい要素9を挿入すると、以下のようになります.
まずcurノードを9に初期化し,9のnextを15に指定する.最後に、6のnextを9に接続すると、下図に示す結果が表示されます.

Add Node at the Beginning

link-listは、リスト全体を表すheadノードを有する.したがって、要素が最初に追加された場合、headノードを更新する必要がある.
1.新しいノードcurノードを新しい値に初期化する.
2.新しいノードcurを元のheadに接続する.
3.curをheadに割り当てる.
上図ではlistの先頭に9を挿入すると仮定します.9という新しいノードを作成し、curのnextを既存のheadに接続します.

次にcurをheadに変更すればいいです.

Delete Operation

linked-listからcurノードを削除したい場合は、どうすればいいですか?
次の段階を経験する必要があるかもしれません.
1.curノードの前のノードprevノードと次のノードnextを見つける必要がある.

2.prevノードのnextをcurからnextノードに変更すればよい.

この過程で、削除操作の時間的複雑さはどうですか?
最初のステップでは、link-listのcurノードのprevおよびnextを検索する必要があります.これはheadからcurに順次アクセスすればよいので、難しいことではありません.しかしlink-listの概念を紹介する際にlistのサイズがNの場合,平均iの最初の要素に近い時間複雑度はO(N)であると述べた.したがって、curへのアクセス時間O(N)はdelete演算の時間的複雑さである.

delete the First Node

最初のノードhead nodeを削除したらどうしますか?これは挿入演算と同様であり、headを更新する必要がある.head人23を下図で削除します.

では、headノードの次のノード6を新しいheadとして指定する必要があります.23を持つノードを削除すればよい.

Array VS Linked-List

シナリオの長所と短所

장점 : 항목 접근 속도가 빠르고 일정하다.

배열은 자료형에 따라 한 배열 항목의 크기가 결정이 된다. 
4byte INT 데이터를 담는 배열을 선언하는 경우, 항목 크기 역시 4byte가 된다. 
배열의 기본 주소는 배열의 맨 처음 부분을 가르키고, 블럭 단위로 메모리를 차지한다. 
따라서 "기본주소 + (자료형의 크기 x Index)"로 특정 인덱스에 위치한 항목에 접근할 수 있다. 
예를 들면 INT 배열 5번 인덱스에 접근할 때에는 (기본주소 + 4 * 5)를 계산한 결과로 나온 메모리를 찾아가면 찾을 수 있다.
따라서 이처럼 위치에 상관없이 한 번의 연산으로 항목을 찾아 갈 수 있어서 접근 속도가 빠르다.

단점 
1. 크기가 고정되어 있다. 사용하기 전에 배열 크기를 지정해야한다.
(물론 동적배열로 해결이 가능하나 동적배열의 경우에도 배열이 꽉차면 기존의 크기의 2배씩 크기를 늘리므로 비효율적이다.)

2. 메모리를 한 덩어리로 차지하므로, 배열 크기가 큰 경우 배열 전체를 위한 메모리를 할당 받지 못하는 경우가 있다.

3. 삽입이 복잡하다.
(배열은 중간에 삽입하려면 우선 기존에 있는 항목들을 밀어내고 해당 공간을 비워야하므로 최대 N번의 항목이동이 발생한다.)

リンクリストの長所と短所

장점 : 삽입이 간단하며 항목 생성 후 포인터 값만 변경해주면 된다.

단점
1. 항목 접근이 오래 걸린다.
첫 항목부터 순차적으로 접근하므로 최소는 O(1)부터 최대 O(N)의 시간이 걸린다.

2. 물리적으로 인접한 메모리에 위치해있지 않다.
배열의 항목은 물리적으로 인접해있어 접근 시간 단축과 캐싱에 유리하다고 하지만 연결리스트는 그렇지 않다.

3. 참조 포인터를 위한 메모리 공간이 낭비된다. 

どのような場合にArrayを使用し、どのような場合にLinked-Listを使用しますか?
格納するデータの数が決定され、リストの真ん中にデータを挿入、削除する操作が多くなく、インデックスを使用して迅速に検索する必要がある場合は、配列を使用することが有効です.
逆に、格納するデータの個数が特定されておらず、リストの中間にデータを挿入、削除する操作が多く、挿入、削除よりも特定の場所のデータを検索する操作が多くない場合は、接続クエリーを使用するとより効果的です.

Single-Linked-List code in Swift

コードの作成はleetcodeで単一リンクリストを実現するページで行われる.実施すべき事項は以下の通りである.

MyLinkedList() Initializes the MyLinkedList object.

int get(int index) Get the value of the index'th node in the linked list. If the index is invalid, return -1 .

void addAtHead(int val) Add a node of value val before the first element of the linked list. After the insertion, the new node will be the first node of the linked list.

void addAtTail(int val) Append a node of value val as the last element of the linked list.

void addAtIndex(int index, int val) Add a node of value val before the index'th node in the linked list. If index equals the length of the linked list, the node will be appended to the end of the linked list. If index is greater than the length, the node will not be inserted.

void deleteAtIndex(int index) Delete the index'th node in the linked list, if the index is valid.

class MyLinkedList {
    
    class Node {
    var data: Int
    var next: Node?
    init(data: Int, next: Node? = nil) {
        self.data = data
        self.next = next
        }
    }
    var head: Node?
    
    init() {
        self.head = nil
    }
    
    func get(_ index: Int) -> Int {
        guard let node = node(at: index) else {
            return -1
        }
        return node.data
    }
    
    func node(at: Int) -> Node? {
        guard at > -1, var node = head else {
            return nil
        }
        guard at > 0 else {
            return head
        }
        for _ in 1...at {
            guard let nextNode = node.next else {
                return nil
            }
            node = nextNode
        }
        return node
    }
    
    func addAtHead(_ val: Int) {
        let newNode = Node(data: val, next: head)
        self.head = newNode
    }
    
    func addAtTail(_ val: Int) {
        guard head != nil else {
            head = Node(data: val)
            return 
        }
        var node = head
        while node?.next != nil {
            node = node?.next
        }
        node?.next = Node(data: val)
    }
    
    func addAtIndex(_ index: Int, _ val: Int) {
        if index <= 0 {
            addAtHead(val)
            return
        }
        guard let prevNode = node(at: index - 1) else {
            return
        }
        let newNode = Node(data: val, next: prevNode.next)
        prevNode.next = newNode
    }
    
    func deleteAtIndex(_ index: Int) {
        if index == 0, head != nil {
            head = head?.next
            return
        }
        guard let prevNode = node(at: index - 1) else {
            return
        }
        prevNode.next = prevNode.next?.next
    }
}

コメントリンク

leetcode single-linked-list
配列と接続リスト