[1주차] 자료구조 - 선형 자료구조

 

 

1주차의 개념 학습 범위는 선형 자료구조, 여기까지다.

스터디에서는 사용하는 언어는 Python3로 결정되어서, 컴퓨터 과학에서의 선형 자료구조를 Python3의 해당 자료구조와 매칭시키는 방식으로 정리를 해보겠다.

 

---

 

🚃 선형 자료구조 (Linear Data Structures)

 

선형 자료구조의 "선형"이라는 말은, 자료구조 내 모든 요소가 1차원적으로 "순서대로" 나열되어 있고, "한 요소를 거쳐야 다음 요소에 접근 가능" 하다는 의미이다.

 

1. 배열 (Array)

 

배열은 같은 자료형의 요소를 연속적인 메모리에 저장하는 구조이다.

여기서 핵심이 밑줄 친 "같은 자료형의 요소"를 "연속적인 메모리"에 저장한다는 부분이다.

 

특징은 아래와 같다.

• 인덱스로 접근이 가능하다, 인덱스를 통해 접근시 시간 복잡도는 O(1)이다.
• 중간에서의 삽입 / 삭제는 O(n)의 시간 복잡도를 갖는다.
  • 삽입은 배열의 맨 뒤에서만 가능하기 때문이다.

 

Python에서는 list가 가장 유사하게 동작하게 된다.

list의 경우 배열과 달리 각기 다른 자료형의 요소를 선형으로 나열할 수 있다는 점에서 차이가 있다.

 

다만, array.array를 사용할 경우 C 언어의 문법과 동일하게 같은 자료형만 선형으로 저장할 수 있다.

 

 

2. 연결 리스트 (Linked List)

 

그림은 단일 연결 리스트.

 

연결 리스트는 각 요소(노드 / Node)가 각각 '데이터'와 '다음 노드의 포인터'로 연결된 구조이다.

 

이게 이중 연결 리스트

이건 원형 연결 리스트

연결 리스트에는 3가지의 종류가 있다.

• 단일 연결 리스트 (Singly Linked List)
  • 다음 노드에 대한 포인터만 담고 있다.
• 이중 연결 리스트 (Doubly Linked List)
  • 이전 노드에 대한 포인터도 갖고 있다.
• 원형 연결 리스트 (Circular Linked List)
  • 마지막 노드가 시작 노드 (Head)를 가리키는 포인터를 갖고있다.

 

특징은 다음과 같다.

• 순차 탐색 시 접근에 O(n)의 시간 복잡도 소요
  • 배열과 동일하게 '연속된 메모리 공간'이 아닐 수도 있기 때문에, 인덱스를 통한 접근은 불가능하며, 해당 노드의 포인터를 찾는 데에 시간이 소요된다.
• 삽입/삭제 시 O(1)의 시간 복잡도 소요
  • 포인터의 연결만 변경해주면 되기 때문이다.
  • 따라서 리스트의 크기는 동적으로 변경될 수 있으며, 효율적인 삽입/삭제가 가능하게 된다.

 

이건 내가 좋아하는 원형 연결리스트 짤

 

Python3에서는 collections 내장 패키지의 dequqe 모듈 (collections.deque)가 부분적으로 유사하다.

내장 패키지에 직접적으로 구현된 연결 리스트는 존재하지 않지만, dequqe를 사용한다면 양쪽에서의 삽입/삭제는 O(1)이지만

중간에서의 삽입/삭제는 O(n)이라는 차이가 존재한다. 이를 이용하면 이중 연결 리스트처럼으로도 사용할 수는 있다.

 

3. 스택 (Stack)

 

LIFO (Last In First Out)의 자료구조이다.

주로 함수 호출 스택이나 괄호검사 등의 구현에 사용이 된다. 후위 표기 연산의 계산에도 쓰인다.

 

스택 자료 구조는 맨 위에 요소를 추가하는 push 연산과 맨 위의 요소를 제거하는 pop 연산을 갖는다.

 

top에 접근, 삽입과 삭제에 O(1)의 시간 복잡도가 소요된다.

 

Python3에서는 list 혹은 collections.deque를 통해 구현이 가능하다.

list는 .append()와 .pop() 메서드를 갖기 때문이다.

큰 데이터의 경우에는 deque를 통해 구현하는 것이 효율적이다.

 

4. 큐 (Queue)

FIFO (First In First Out)의 자료구조이다.

스택이 자료구조의 맨 위에서만 삽입과 삭제 연산이 가능했다면, 큐는 삽입은 앞에서, 삭제는 뒤에서 이뤄진다.

 

큐 자료구조는 맨 앞에서 요소를 추가하는 enqueue 연산과 맨 뒤에서 요소를 제거하는 dequeue 연산을 갖는다.

 

front와 back에 접근, 삽입과 삭제에 O(1)의 시간 복잡도를 갖는다.

 

Python3에서는 collections.deque를 통해 기본적으로 사용할 수 있다.

append() + popleft()를 통해 구현이 가능하다.

 

추가적으로 큐에서 삽입과 삭제가 front와 back에서 모두 이뤄질 수 있도록 할 수 있는 것이 덱 (deque) 라는 녀석이다.

 

 

---

 

😇 마치며

 

대학을 다닐때, 정보처리기사를 공부할 때... 그렇게 지겹도록 봐 온 자료구조인 것 같다.

C++17을 사용한다면, STL을 통해 전통적인 컴퓨터과학에서의 자료구조를 모두 이용할 수 있을 텐데

이 모든 자료구조가 Python3의 내장 패키지에는 전부 구현되어있지 않아서 Python3를 사용한 스터디에서 조금 혼선이 생길 것 같다...