선형 자료구조

선형 자료구조

- 데이터를 순차적으로 저장 (각 데이터가 1:1로 연결되는 방식)

- 배열, 링크드 리스트, 스택, 큐

---

배열

연속적인 메모리 공간에 순차적으로 저장되는 자료구조

 

특징

- 모든 요소가 같은 타입

>>> 연속적인 메모리 공간에 데이터들이 존재하고, 데이터들의 타입이 같으니 O(1)로 시간 복잡도로 랜덤 접근 가능

- Sequence와 Collection 프로토콜을 채택하고 있는 컬렉션 타입

 

Capacity

- 새로운 저장공간 없이 배열이 포함할 수 있는 요소의 개수

- 초기화 시점에 요소의 개수만큼 capacity 설정

- capacity를 넘어가게 되면 기존 capacity의 약 2배 크기의 새로운 공간을 만든 후 기존 배열을 복사하고 요소 추가

- reserveCapacity 메서드를 활용하여 불필요한 배열 복사 리소스 줄일 수 있음

---

링크드 리스트

- 불연속적인 메모리 공간에 순차적으로 저장되는 자료구조

- 데이터 + 포인터(다음 데이터의 주소)로 구성된 노드로 구성

특징

- 동적 크기 조정 가능

- 데이터 접근은 느리지만 삽입 삭제가 빠름

- 원소에 접근하기 위한 링크드 리스트 순회 => O(N)

- 추가 제거의 경우 => O(1)

---

스택(Stack)

- 데이터의 삽입, 삭제가 한쪽 끝에서만 이루어지는 자료구조 => 선입후출 형식

특징

- 작업이 주로 push, pop, peek 으로 이루어짐

 

활용 사례

- 이전 상태로 되돌리는데 특화

- DFS

- 브라우저 뒤로가기

 

코드 구현

struct Stack<T> {

	private var elements: [T] = []
	init() {}
	
	mutating func push(with element: T) {
		elements.append(element)
	}
	
	@discardableResult
	mutating func pop() -> T? {
		elements.popLasa()
	}
	
	func peek() -> T? { 
		elements.last
	}
	
	var isEmpty: Bool {
		elements.isEmpty
	}
	
	var count: Int {
		elements.count
	}
}

---

QUEUE(큐)

- 선입선출 형식의 자료구조

 

특징

- 작업이 주로 enqueue, dequeue

 

활용 사례

- 프로세스 스케줄링

- BFS

- 네트워크 데이터 패킷 처리

 

코드 구현

struct Queue<T> {
	
	private var enqueueStack: [T] = []
	private var dequeueStack: [T] = []
	
	var isEmpty: Bool {
			return enqueueStack.isEmpty && dequeueStack.isEmpty
	}
	
	mutating func enqueue(elements: T) {
		enqueueStack.append(elements)
	}
	
	mutating func dequeue() -> T? {
		if dequeue.isEmpty {
				dequeueStack = enqueueStack.reversed()
        enqueueStack.removeAll()
		}
	   return dequeueStack.popLast()
	}
}