자료 구조 - 배열, 연결 리스트

C언어로 쉽게 풀어쓴 자료구조를 읽으며 정리

---

배열

• 인덱스와 요소 쌍의 집합
• 메모리의 연속된 위치에 구현된다.
• 크기 5인 배열 A가 있을 때 메모리 주소는 아래와 같다.

Element	Memory Address
A[0]	base * 1 * sizeof(type of Element)
A[1]	base * 2 * sizeof(type of Element)
A[2]	base * 3 * sizeof(type of Element)
A[3]	base * 4 * sizeof(type of Element)
A[4]	base * 5 * sizeof(type of Element)

 

 

함수의 매개 변수로서의 배열

• C언어에서 함수의 매개 변수로 배열을 전달하는 것은, 배열의 포인터가 전달되는 것과 같다.
• Swift 역시 배열 자체가 아닌 배열의 참조가 전달된다.
• Swift에서의 배열은 Value 타입이다. 즉 배열을 변수에 할당하거나 메서드에 전달할 때 배열의 복사본이 전달된다.
• Swift는 Copy-On-Write 방식을 사용한다. (복사는 배열이 수정될 때만 발생된다)

장점

• Random Access
• 인덱스로 특정 요소에 접근 시간 복잡도는 O(1)

단점

• 삽입, 삭제 시간 복잡도는 O(n)

Swift에서 삽입 삭제 메서드

• append(_:) : 평균 O(1), 최악 O(n)
• insert(_:at:) : i가 중간 위치라면 O(1), 맨 끝이라면 append와 동일
• removeLast() : 항상 O(1)
• remove(at:) : 문서에는 O(n)으로만 나와있는데, 마지막 위치라면 O(1)이 될 것임.

마지막 위치의 삽입에서도 최악의 경우 O(n)의 시간 복잡도가 걸리는 이유

 

Swift 배열은 동적 배열이다.

 

배열은 일정 크기만큼 메모리를 할당한 다음, 그 크기가 초과되면 메모리 크기를 두 배로 늘린다. 배열의 크기와 저장 용량(capacity)가 동일해진 경우 현재 용량의 두 배 크기의 새로운 메모리 블록을 할당할 것이다.이 과정에서 기존 메모리 블록의 모든 요소들이 새로운 메모리 블록으로 복사되므로 O(n)의 시간 복잡도가 소요된다.

 

var greeting = "Hello, playground"

var array = [Int]()
for i in 1...8 {
    array.append(i)
    print("Array count: \(array.count), capacity: \(array.capacity)")
}

array.append(9) // This will trigger a reallocation
print("After appending 9, count: \(array.count), capacity: \(array.capacity)")

//Array count: 1, capacity: 2
//Array count: 2, capacity: 2
//Array count: 3, capacity: 4
//Array count: 4, capacity: 4
//Array count: 5, capacity: 8
//Array count: 6, capacity: 8
//Array count: 7, capacity: 8
//Array count: 8, capacity: 8
//After appending 9, count: 9, capacity: 16

 

연결 리스트

각 요소(Element)와 링크의 쌍인 노드에 분산 저장하는 자료구조이다.

• 배열과 다르게 메모리 내 노드의 물리적인 순서와 논리적인 순서가 일치하지 않는다.
• 연속적인 메모리 공간이 없어도 데이터 저장이 가능
• 링크를 위한 추가 공간 필요
• 트리 구조의 근간이 되는 자료구조

 

시간 복잡도

• 탐색 - 시간 복잡도 O(n)
• 삽입,삭제 - 시간 복잡도 O(1)

 

n의 크기가 아주 크고, 삽입, 삭제가 빈번하게 일어나는 케이스에 대해 연결 리스트를 고려해보면 좋겠으나

앞으로 연결 리스트를 고려해볼만한 상황이 생길지 잘 모르겠다.

 

단순 연결 리스트

 

• 노드 당 하나의 링크 필드
• 마지막 노드의 링크 필드 값은 Null
• 삽입과 삭제는 단순히 노드의 링크를 변경해주면 된다.

 

원형 연결 리스트

• 마지막 노드의 링크 필드 값이 첫 번째 노드가 된다.
• 임의의 하나의 노드에서 어떠한 노드로도 갈 수 있다.
• 헤드가 마지막 노드를 가리키게 하면 처음이나 마지막 노드 삽입 연산이 유리해진다.

이중 연결 리스트

 

• 각 노드가 선행/후행 노드 두 개의 링크를 가져 양방향 탐색이 가능하다.
• 추가적인 공간 필요

 

연결 리스트 swift 구현은 생략