[Data Structure] Linked List (Feat. Array)

배열 (Array)이란?

• 원소들이 메모리에 연속적으로 저장된 자료구조
• 인덱스로 배열의 원소를 바로 찾을 수 있다.

배열의 특징

• O(1)에 n번째 원소를 확인하고, 변경할 수 있다.
• 추가적으로 소모되는 메모리의 양, 즉 오버헤드가 거의 없다.
• 메모리 상에 데이터들이 붙어있기 때문에, Cache hit rate가 높다.
• 메모리 상에 연속적으로 구간을 잡아야하므로, 할당에 다소 제약이 있다.
  • 배열의 첫번째, 마지막 인덱스 이외의 인덱스에 새롭게 원소를 추가하거나 제거할 때, 원소들을 새롭게 배치해야하기 때문.
    ㅤ

연결 리스트 (Linked List)란?

• 메모리 상에 연속적이지 않은 데이터들을 링크로 연결해놓은 자료구조
• 연결 리스트는 노드로 이루어져있는데, 노드는 data (데이터), link (링크)로 이루어져있다.
  • data에는 데이터가, link에는 다음에 올 데이터의 주소값이 저장된다.
• 노드들이 연결되어 이루어진 것이 연결 리스트.
•  
• 

연결 리스트의 특징

• n번째 원소를 확인/변경할 때의 시간 복잡도는 O(n)이다.
• 임의의 위치에 원소를 추가/삭제할 때의 시간 복잡도는 O(1)이다.
• 원소들이 메모리 상에 연속적으로 저장되어있지 않기 때문에, Cache hit rate가 낮지만 할당이 다소 쉽다.

연결 리스트의 임의의 위치에 원소 추가/삭제하기

• 시간 복잡도 = O(1)
• 연결 리스트에서 2번째 위치에 원소 추가하기
  • 첫번째 원소가 새로 추가되는 원소를 가리키도록 하고, 새로 추가되는 원소는 원래 2번째 위치에 존재하던 원소를 가리키도록 한다.
• 연결 리스트에서 2번째 위치에 존재하는 원소 제거하기
  • 첫번째 원소가 2번째 원소가 아닌 세번째 원소를 가리키도록 하기

연결 리스트의 종류

• 단일 연결 리스트 (Singly Linked List)
  • 각 원소가 자신의 다음 원소의 주소를 갖는다.
  • 주어진 원소의 이전 원소가 무엇인지 알 수 없다.
• 이중 연결 리스트 (Doubly Linked List)
  • 각 원소가 자신의 이전 원소와 다음 원소의 주소를 모두 갖는다.
  • 주어진 원소의 이전 원소가 무엇인지 알 수 있다.
  • 원소가 갖고 있는 정보가 단일 연결 리스트보다 1개 더 늘어나므로, 메모리가 더 든다는 단점이 있다.
• 원형 연결 리스트 (Circular Linked List)
  • 리스트의 끝이 처음과 연결되어있다.
  • 각 원소가 자신의 이전 원소와 다음 원소의 주소를 모두 갖고 있어도, 없어도 상관이 없다.

ㅤ

ㅤ

배열 vs 연결 리스트

ㅤ

야매 연결 리스트 구현하기

원소를 배열로 관리하고 pre와 nxt에 이전/다음 원소의 포인터 대신 배열 상의 인덱스를 저정하는 방식으로 구현한 연결 리스트.

let MX = 100
var dat = [Int](repeating: 0, count: MX) // 데이터 저장
var pre = [Int](repeating: -1, count: MX) // 이전 주소 (인덱스) 저장
var nxt = [Int](repeating: -1, count: MX) // 다음 주소 (인덱스) 저장
var unused = 1 // 현재 사용되지 않는 인덱스 (새로운 원소가 들어갈 수 있는 인덱스)로, 원소 추가 이후에는 1씩 증가

• dat[i] : i번지 원소의 값
• pre[i] : i번지 원소에 대해 이전 원소의 인덱스
• nxt[i] : i번지 원소에 대해 다음 원소의 인덱스
• pre나 nxt의 값이 -1이면 해당 원소의 이전/다음 원소가 존재하지 않는다는 뜻이다.
• unused : 현재 사용되지 않는 인덱스. 즉 새로운 원소가 들어갈 수 있는 인덱스로, 원소가 추가된 이후에는 1씩 증가될 것이다.
• 0번지는 연결 리스트의 시작 원소로 고정. 다르게 말하자면 0번지에는 값이 들어가지 않고 단지 시작점을 나타내기 위한 dummy node이다.
• 길이가 따로 필요하다면, len 변수를 따로 만들고 원소가 추가될 때 1씩 증가시키고, 제거될 때 1씩 감소시키면 된다.

traverse 함수 - 연결 리스트의 모든 원소들 출력하기

• 0번지에서 출발해서 nxt에 적힌 값을 보고 계속 넘어가면서 dat를 출력하면 된다.
• cur라는 변수에 각 원소들의 주소를 담아가면서 이동하는 방식으로, cur에 -1이 저장되면 끝에 도달했다는 뜻이므로 while문을 탈출하고 traverse가 종료된다.

/// 연결 리스트의 모든 원소들을 출력 (연결 순서대로 출력)
func traverse() {
    var cur = nxt[0]
    while cur != -1 {
        print(dat[cur], terminator: " ")
        cur = nxt[cur]
    }
    print("** traverse 끝 **")
}

insert 함수 - 연결 리스트에 원소 삽입하기

• 새 원소를 생성한다. 이 때 unused 값이 새로운 원소가 들어갈 인덱스가 된다.
• 새 원소의 pre 값에 삽입할 위치의 주소 (인덱스)를 대입한다.
• unused가 가리키는 곳이 새로운 원소가 들어갈 자리. 그 자리의 dat에 값을 넣어주면 된다.

/// 예를 들어 원소 13이 2번지이고 13 뒤에 20을 새로 추가하고 싶은거면 insert(2, 20)을 호출
/// unused가 가리키는 곳이 새로운 원소가 들어갈 자리. 그 자리의 dat에 값을 넣어주면 된다.
/// - Parameters:
///   - addr: 추가하려는 원소의 위치 (주소, 인덱스, 번지)
///   - num: 추가할 값
func insert(addr: Int, num: Int) {
    // 1. 새로운 원소 생성
    dat[unused] = num

    // 2. 새 원소의 pre 값에 삽입할 위치 (주소) 값 저장
    pre[unused] = addr

    // 3. 새 원소의 nxt 값에 삽입할 위치의 nxt 값 저장
    nxt[unused] = nxt[addr]

    // 4. 새롭게 들어간 원소의 자리에 원래 있던 원소의 nxt 값과 삽입할 위치의 다음 원소의 pre 값을 새 원소로 변경
    // (삽입할 위치의 nxt 값과 삽입할 위치의 다음 원소의 pre 값을 새 원소로 변경)
    if nxt[unused] != -1 { // 새로 삽입한 원소가 마지막이 아닐 경우에만!
        pre[nxt[addr]] = unused
    }
    nxt[addr] = unused
    unused += 1
}

erase 함수 - 연결 리스트에 원소 삽입하기

• 이전 원소의 nxt를 삭제하려는 원소의 nxt로 변경한다.
• 다음 원소의 pre를 삭제하려는 원소의 pre로 변경한다. 삭제하려는 원소가 마지막 원소가 아닐 경우에만 이 작업을 진행한다.

///  원소 13이 2번지이고, 13을 지우고 싶으면 erase(2)를 호출
/// - Parameter addr: 지우려는 원소의 위치 (주소, 인덱스, 번지)
func erase(addr: Int) {
    // 1. 이전 원소의 nxt를 삭제하려는 원소의 nxt로 변경
    nxt[pre[addr]] = nxt[addr]

    // 2. 다음 원소의 pre를 삭제하려는 원소의 pre로 변경.
    if nxt[addr] != -1 { // 삭제하려는 원소가 마지막 원소가 아닐 경우에만!
        pre[nxt[addr]] = pre[addr]
    }
}

전체 야매 연결 리스트 코드

import Foundation

let MX = 100
var dat = [Int](repeating: 0, count: MX
var pre = [Int](repeating: -1, count: MX)
var nxt = [Int](repeating: -1, count: MX)
var unused = 1

func insert(addr: Int, num: Int) {
    dat[unused] = num
    pre[unused] = addr
    nxt[unused] = nxt[addr]

    if nxt[unused] != -1 {
        pre[nxt[addr]] = unused
    }
    nxt[addr] = unused
    unused += 1
}

func erase(addr: Int) {
    nxt[pre[addr]] = nxt[addr]

    if nxt[addr] != -1 {
        pre[nxt[addr]] = pre[addr]
    }
}

func traverse() {
    var cur = nxt[0]
    while cur != -1 {
        print(dat[cur], terminator: " ")
        cur = nxt[cur]
    }
    print("** traverse 끝 **")
}

print("😇insert test😇")
insert(addr: 0, num: 10)
traverse() // 10(address=1)
insert(addr: 0, num: 30)
traverse() // 30(address=2) 10
insert(addr: 2, num: 40)
traverse() // 30 40(address=3) 10
insert(addr: 1, num: 20)
traverse() // 30 40 10 20(address=4)
insert(addr: 4, num: 70)
traverse() // 30 40 10 20 70(address=5)

print("\n😇erase test😇")
erase(addr: 1)
traverse() // 30 40 20 70
erase(addr: 2)
traverse() // 40 20 70
erase(addr: 4)
traverse() // 40 70
erase(addr: 5)
traverse() // 40

ㅤ
ㅤ

출처