Array, Linked List

배열 Array

• 연관된 데이터를 하나의 변수에 그룹핑해서 관리하기 위한 방법
• 메모리 상에서 데이터를 연속적으로 저장하는 것이 특징

장점

• 배열을 이용하면 하나의 변수에 여러 정보를 담을 수 있고, 반복문과 결합하면 많은 정보도 효율적으로 처리 가능
• 데이터가 연속적으로 저장되어있기 때문에 index를 통한 접근이 가능

단점

• 배열의 크기는 선언할 때 고정되어야 함
• 데이터를 연속적으로 유지해야하기 때문에 삽입/삭제가 오래 걸림
• 배열 중간에 있는 데이터가 삭제되면, 공간 낭비가 발생함

동적배열이란?

동적배열

배열의 크기는 선언할 때 고정되어야 하기 때문에 동적으로 크기를 변경하는 것이 사실 어렵지만 가능하다.

동적 배열은 초기에 작은 크기의 배열을 선언하고 데이터가 추가될 때마다 크기를 동적으로 확장시키는 방법이다.

동적배열의 원리

동적 배열은 초기에 작은 크기의 배열을 할당하고, 배열에 데이터가 추가될 때마다 배열의 크기를 동적으로 늘리는 방식으로 동작한다.

이때, 새로운 배열이 더 큰 메모리 공간에 할당되고, 기존 배열의 모든 요소가 새로운 배열로 복사된다. 이 과정에서 새로운 배열의 크기가 연속적으로 할당되는 메모리 영역을 갖는다.

따라서, 동적 배열도 일반적인 배열과 마찬가지로 메모리상에서 연속적인 공간에 요소들이 할당되어 있다. 그러나 동적 배열의 크기를 동적으로 변경할 수 있기 때문에, 배열의 크기가 변하는 동안에도 메모리상에서 연속적인 공간을 유지하기 위해 추가적인 메모리 할당과 복사 작업이 필요하다는 단점이 있다.

 

연결리스트(Linked List)

• 여러 개의 노드들이 순차적으로 연결된 형태를 갖는 자료구조이며, 첫번째 노드를 head, 마지막 노드를 tail이라 함
• 각 노드는 데이터와 다음 노드를 가리키는 포인터로 구성 됨
• 배열과는 다르게 메모리를 연속적으로 사용하지 않음
• Tree 구조의 근간이 되는 자료구조이며, Tree 에서 사용되었을 때 그 유용성이 드러남

노드

한 개의 노드는 저장할 데이터, 다음 노드를 가리키는 포인터(메모리 주소) 두개의 정보를 가지고 있는 구조체

장점

• 배열과는 다르게 순차적으로 접근해야 하는 면에서 불리할 수도 있으나, 노드가 연결된 구조이기 때문에 삽입, 삭제에 용이 함
• 크기를 동적으로 조절할 수 있음

단점

• 배열과는 다르게 인덱스로 데이터 접근이 불가능하여 처음부터 탐색을 진행해야 함
• 각 노드마다 포인터를 가지고 있기 때문에 메모리 공간의 소비가 배열보다 큼

연결 리스트의 종류(단일, 이중, 원형)

연결 리스트

단일 연결리스트

• 각 노드는 데이터와 다음 노드를 가리키는 포인터로 이루어짐
• 데이터 삽입, 삭제가 용이하고 메모리 사용량이 다른 연결 리스트보다 적음
• 데이터의 탐색이 선형적으로 이루어져 탐색 시간이 길어짐

이중 연결리스트

• 각 노드는 데이터와 이전 노드, 다음 노드를 가리키는 포인터로 이루어짐
• 데이터의 삽입, 삭제, 탐색이 빠르며 양방향으로 탐색이 가능함
• 메모리 사용량이 많아 단일 연결리스트보다 많은 메모리를 사용함

원형 연결리스트

• 단일 연결리스트와 유사하지만 마지막 노드가 첫 번째 노드를 가리키는 포인터를 가지고 있어 원형으로 연결된 구조로 이루어짐
• 마지막 노드와 첫 번째 노드를 구분하지 않아도 되므로 일정한 작업 수행 시간을 보장할 수 있음

 

배열과 연결리스트

배열과 연결리스트 중 어떤걸 사용해야하는가?

• 배열의 특성: 정적인 데이터 구조를 가지고 있으며, 메모리를 연속적으로 사용하여 각 데이터 접근이 편리함
• 연결 리스트의 특성: 메모리를 연속적으로 사용하지 않아 데이터 추가 및 삭제가 용이함

데이터가 작고 크기가 변하지 않는 경우 → 배열

데이터가 많이 추가, 삭제되는 동적인 데이터 → 연결 리스트

Swift의 배열

• Swift에서 사용하는 Array는 기본적으로 동적배열을 사용한다. Swift에서는 배열에 데이터를 보관할 때 특정 양의 메모리를 예약하는데, 만약 배열이 예약된 용량을 초과하기 시작하면 배열은 더 큰 메모리 영역을 할당하고 해당 요소를 새 저장소에 복사한다. 이때 새 저장소의 공간은 이전 저장소 크기의 배수로 증가한다.
• Swift에서 동적 메모리 공간을 할당하는 방식은 한번 확장할 때 충분한 공간을 할당해놓고 데이터를 한번 새로운 공간에 복사하고 사용하기 위함이다. 매번 확장될 때마다 필요한 양만큼만 메모리 공간을 새로 할당하고 데이터를 다시 복사하고 이전 메모리 공간을 해제하는 방식은 시간이 오래 소요되기 때문이다.

Array와 NSArray의 차이점

• Swift에서 **Array**와 **NSArray**는 모두 데이터를 순서대로 저장하는 컬렉션 타입이지만, 내부적으로 구현된 방식과 제공하는 기능 등에 차이가 있다.
  • Array
    • Swift의 기본 배열 타입으로, 제네릭 타입으로 구현되어 있다. 내부적으로는 동적 배열(dynamic array)로 구현되어 있어, 처음 배열을 생성할 때 크기를 지정하지 않아도 되며, 배열의 크기가 자동으로 조절된다.
    • 값 타입(Value Type)으로 구현되어 있으므로, 배열을 복사할 때 내부적으로 데이터를 복사한다.
    • 비교적 속도가 빠르지만 객체를 저장할 수 없다.
  • NSArray
    • Objective-C에서 제공하는 배열 타입으로, 클래스 타입으로 구현되어 있다. 제네릭 타입이 아닌 ‘id’ 타입(클래스 인스턴스의 포인터)을 이용해 모든 객체를 저장할 수 있다.
    • 내부적으로는 연결 리스트(linked list)로 구현되어 있어, 배열의 크기를 동적으로 조절할 필요가 없으며, 객체가 추가될 때마다 새로운 노드를 생성한다. 인덱스를 통한 접근이 느리지만, 객체의 추가와 삭제가 빈번한 경우에는 Array 보다 성능이 우수하다.
    • 참조 타입(Reference Type)으로 구현되어 있으므로, 배열을 복사할 때는 데이터를 복사하는 대신에 참조를 복사한다. 객체를 저장할 수는 있지만 객체의 추가, 삭제가 빈번한 경우 속도 차이가 존재한다.

---

출처

열혈 C프로그래밍(윤성우 저)

열혈 자료구조(윤성우 저)

https://docs.swift.org/swift-book/documentation/the-swift-programming-language/collectiontypes/#Arrays

이미지 출처

[자료구조] 리스트 구현 - 연결리스트(단순 연결리스트) — yjglab (tistory.com)

자료구조 링크드리스트(Linked list) (tistory.com)