[Data Structure] Array & Linked List(1) - Concept

이번 포스팅에선 선형 자료구조의 배열과 연결 리스트에 대해서 알아보자. 

 

List(Sequence) ADT 

List 혹은 Sequence는 추상 자료형(Abstract Data Type)으로

Data의 중복을 허용하는 순서가 있는 Data의 모임이다.

추상 자료형은 기능만을 명세해 놓은 것이다. 이를 구현한 것이 자료구조가 된다.

 

이러한 List ADT는 다음과 같은 기능을 명세한다. 

• 처음, 끝, 혹은 중간에 데이터를 추가 / 삭제하는 기능 
• 데이터가 있는지를 체크하는 기능 
• 모든 데이터에 접근할 수 있는 기능

이때 데이터를 <index, value>쌍으로 저장하면 동적배열(Dynamic Array)이 

각 데이터들을 포인터를 통해 연결하면 연결리스트가 된다. 

 

 

배열 (Array)

"배열"(Array)은 <index, value>쌍으로 구성되며 메모리 상에서 연속적으로 배치되어져 있다. index를 통해 원하는 값으로 접근이 가능하다.

이때 배열의 크기를 고정여부에 따라서 "정적 배열"(Static Array)와 "동적 배열"(Dynamic Array)로 구분된다.

 

정적 배열 (Static Array)

"정적 배열"(Static Array)은 배열의 크기가 고정되어 있으며, compile time에 결정 난다. 대표적으로 C언어에서 기본적으로 제공하는 배열이 여기에 해당된다. 

int arr[4];
int arr[] = {1, 2, 3};

 

동적 배열 (Dynamic Array)

"동적 배열"(Dynamic Array)는 List ADT의 일종으로 배열의 크기가 가변적이다. 

 

Static Array는 크기가 고정적이기에 원소의 추가나 삭제가 불가능하다. 따라서, List의 장점을 Array 합친 것이 Dynamic Array이다.

Java에선 ArrayList, C++에선 vector가 여기에 포함된다. 

vector<int> v; 
v.push_back(1);

 

동적 배열의 경우, 연속적인 메모리 공간을 할당하다가 사이즈가 더 커지게 된다면, 

새로운 공간을 할당해 복사하는 작업을 진행한다. 

 

따라서, 배열의 마지막 원소 추가는 O(1)이지만, 재할당하는 경우 복사하는 작업에 의해 O(N)의 시간이 걸릴 수 있다. 

 

Swift Array 

Swift의 Array는 Dynamic Array만을 제공한다. 

var numbers = [1, 2, 3, 4, 5] // Dynamic Array

 

이러한 Swift의 Array는 Collection프로토콜을 채택하고 있는데, Collection 프로토콜은 Sequence프로토콜을 채택하고 있다. 

 

Sequence

Sequence Protocol은 element에 순차적이고 iterate하게 접근할 수 있는 타입이다.

protocol Sequence<Element>

해당 Protocol은 required method로는 makeIterator()가 있지만,

다음과 같이 흔히 사용하는 여러 method가 extension으로 구현되어져 있다. 

• map, filter, first, dropFirst, dropLast ...

Sequence의 특징은 다음과 같다. 

• 무한할 수 있다. 그렇기 때문에, 몇개의 element가 있는지 알 수 없다.
• 여러번의 반복을 보장하지 않는다. 

for element in sequence {
    if ... some condition { break }
}

for element in sequence {
    // No defined behavior
}

보통 다음과 같은 상황에서, 2번째 루프에선 첫번째 element부터 시작할거라고 예상한다.

하지만, Sequence는 처음부터 시작할지 중단된 element부터 시작할지 보장하지 않는다.

 

Collection 

Collection은 Sequence와 달리 유한하다. 즉, element의 갯수를 알 수 있다. 또한, Collection은 여러번의 반복을 보장하고, index를 통해 각 element에 접근이 가능하다.

protocol Collection<Element> : Sequence

Sequence 프로토콜을 채택하기 때문에, Sequence가 제공하는 기능은 모두 제공한다. 

 

 

연결리스트 (Linked List)

"연결리스트"는 각 Node(Element)를 "연결(link)"을 이용해 List ADT를 구현한 것을 의미한다.

이때 각 Node는 다음 Node의 포인터를 저장하는데, 이를 통해 각 Node들이 연결된다. 

 

가장 처음 노드를 Head노드라 부른다.

 

vs. 동적 배열 (Dynamic Array)

둘 다 List ADT를 구현한 자료구조이지만 다음과 같은 차이점이 있다. 

"배열"의 경우에는 각 데이터들이 메모리 상에서 연속적으로 위치한다. 따라서, 첫번째부터 몇번째 데이터임을 나타내는 인덱스를 통해 접근이 가능했다. 

"연결리스트"는 각 데이터들이 메모리 상에 연속적으로 위치하지 않는다. 따라서, 현재 Node는 포인터를 통해 다음 Node를 가리킨다.

 

"배열"의 경우에 탐색은 인덱스를 통해 O(1)이라는 시간에 접근이 가능하지만, 

"연결리스트"는 원하는 노드가 나올 때까지 포인터를 통해 다음 노드로 이동해야 한다.

즉, O(N)의 시간 복잡도가 걸린다.

배열의 경우, 지역성 Locality에 의해 Cache hit Ratio가 높다.

 

중간의 원소 삭제/삽입의 경우, "동적 배열"은 뒤에 노드를 앞으로 땡기거나 밀어야 하기 때문에  O(N)이 소요된다. 

"연결리스트"는 다음과 같이 포인터만 변경해주면 되기 때문에, O(1)이 소요된다.

 

	동적 배열	연결리스트
중간 원소 삭제 / 삽입	O(N)	O(1)
탐색	O(1)	O(N)

 

 

단일 연결 리스트 (Simple Linked List)

가장 기본적인 형태의 단순 연결 리스트는 다음 노드만을 포인터를 통해 가리킨다. 

 

삽입

"단순 연결 리스트"에서 삽입은

삽입되어질 이전 위치의 노드를 안다면 O(1)에 수행이 가능하다.

 

다음과 같이 12값을 가지는 노드를 "Node A" 뒤에 삽입해보자.

• "새로운 노드"의 next를 기존의 "Node A"의 next로 지정한다.
• 우선, Node A의 next를 "새로운 노드"를 가리킨다. 

func insert(_ data: T, after node: Node) {
	let newNode = Node(data: data)
	
	// 새로운 노드의 포인터를 이전 노드의 포인터로 지정.
	newNode.next = node.next
	// 이전 노드의 포인터를 새로운 노드로 지정.
	node.next = newNode
}

 

중간이 아닌 가장 앞에 삽입하는 경우라면 Head 포인터를 새로운 노드로 지정하면 된다.

 

삭제

삭제도 마찬가지로 삭제할 노드의 이전 위치를 안다면, O(1)에 수행이 가능하다. 

• "삭제될 이전 위치의 노드"의 next를 "삭제할 노드"의 next로 지정한다.

func remove(after node: Node) -> T? {
	let removeNode = node.next
	node.next = removeNode?.next
	
	return removeNode?.data
}

 

원형 연결 리스트 (Circular Linked List)

"원형 연결 리스트"는 마지막 노드가 첫 번째 노드를 가리키는 연결리스트이다.

 

원형 연결 리스트는 하나의 노드에서 모든 노드로의 접근이 가능하다는 장점을 가지고 있다. 

 

원형 연결 리스트에서 중간에 삽입 / 삭제는 "단순 연결 리스트"와 동일하다.

반면, 맨 앞과 맨 뒤에서의 삽입 / 삭제는 원형으로 이어주어야 하기 때문에 조금 다르게 수행이 된다. 

 

이중 연결 리스트 (Double Linked List)

"단순 연결 리스트"는 후속 노드에 접근하기는 쉽지만, 선행 노드에 접근하기는 어렵다.

"이중 연결 리스트"는 다음 노드와 이전 노드에 대한 포인터를 들고 있다.

양방향으로 탐색이 가능하기 때문에, 단순 연결 리스트에 비해 탐색 시간에 있어서 장점이 있다.

 

물론 이전 노드에 대한 포인터도 추가되기 때문에, 메모리를 더 많이 사용한다는 점과 구현이 복잡하다는 단점이 있다.

그럼에도 장점이 훨씬 크기 때문에 대부분의 연결리스트는 이중 연결 리스트이다.

 

삽입

값이 20인 노드와 값이 12인 노드 사이에 새로운 노드를 추가하는 상황을 살펴보자. 

 

우선, "새로운 노드"의 next와 prev를 20과 12인 노드로 지정한다.

 

 

이후, "20인 노드"의 next를 "12인 노드"의 prev를 "새로운 노드"로 지정하면 삽입이 종료된다.

 

 

 

삭제 

20과 12사이에 있는 "30인 노드"를 삭제하는 과정을 살펴보자.

 

다음과 같이 "20인 노드"의 next를 "12인 노드"로 지정하고, 

"12인 노드"의 prev를 "20인 노드"로 지정한다.

이후 30인 노드를 메모리에서 해제해주면, 삭제가 종료된다.

 

 

References

위키백과 

• Abstract Data Type
• List(abstract data type)
• Array(data type)
• Array(data structure)
• Linked List

 

애플 공식문서

• Sequence
• Collection
• Array