자료구조: 배열, 연결리스트, 스택, 큐

자료구조란, 데이터를 효율적으로 저장하고, 관리하며, 사용하기 위한 구조입니다. 그 중에서도 가장 기본이 되는 자료구조는 배열, 연결리스트, 스택, 큐, 트리, 그래프이죠. 어떤 자료구조를 쓰느냐에 따라 프로그램의 성능이 크게 달라질 수 있습니다. (앞선 파트에서 자세하게 설명한 바 있습니다.) 

자료구조란? (feat. 시간복잡도, 공간복잡도)

 

이 자료구조들은 프로그래밍에서 가장 많이 사용되는 구조이기 때문에 이해하고 숙지하는 것이 중요합니다. 오늘은 배열, 연결리스트, 스택, 큐까지만 알아보고 다음 파트에서 나머지 트리와 그래프에 대해서도 설명드리겠습니다.

 

 

1. 배열(Array)

배열은 데이터를 일정한 크기로 묶어서 메모리에 연속적으로 저장하는 자료구조입니다. 이때, 각 데이터의 인덱스를 통해 데이터에 접근할 수 있습니다. 배열의 장점은 인덱스를 이용해 빠르게 접근할 수 있다는 것입니다. 그러나 배열은 미리 크기를 정해놓아야 한다는 단점이 있습니다. 그래서 배열이 가득 차는 경우 새로운 데이터를 추가할 수 없거나 기존 데이터를 삭제해야할 수 있습니다.

 

배열의 시간복잡도

• 데이터 접근(탐색, 업데이트): 인덱스를 알고 있기 때문에 O(1)의 시간복잡도를 가집니다. 
• 데이터 삽입:
  • 1) 추가하려는 데이터가 맨 뒤가 아닌 경우: 모든 데이터를 한 칸씩 미뤄야 하므로 O(N)
  • 2) 추가하려는 데이터가 맨 뒤이고, 배열에 공간이 남아있는 경우: O(1)
• 데이터 삭제:
  • 1) 삭제하려는 데이터의 위치가 맨 뒤가 아닌 경우: O(N)
  • 2) 삭제하려는 데이터의 위치가 맨 뒤이고, 배열에 공간이 남이있는 경우: O(1)

 

배열의 사용 예시

배열은 데이터를 연속적으로 저장하고, 빠른 접근이 필요한 경우에 적합합니다. 예를 들어, 정렬된 데이터에 추가적인 데이터를 저장하거나, 특정 데이터를 검색하는 작업에 유용합니다. 

 

---

2. 연결리스트(Linked list=List)

연결리스트는 데이터를 노드(Node)로 구성하여 각 노드가 데이터와 다음 노드를 가리키는 주소를 가지고 있는 자료구조입니다. 즉, 데이터를 저장할 노드가 메모리 상에서 연결되어 있습니다. 이때, 첫번째 노드를 헤드(Head)라 하고, 마지막 노드는 NULL 값을 가리킵니다. 연결리스트의 장점은 가변적인 길이를 가지고 있어서 데이터의 추가, 삭제가 용이하고, 다양한 데이터 타입을 포함할 수 있다는 것입니다. 그러나 연결리스트는 인덱스로 바로 접근하는 것이 불가능하며, 포인터가 여러개 필요하기 때문에 메모리 사용량이 더 크다는 단점이 있습니다. 또 하나의 특징은 아래와 같이 연결 형태에 따라 단순 연결리스트, 원형 형결리스트, 이중 연결리스트 등으로 나타낼 수 있습니다.

 

 

연결 리스트의 시간복잡도

• 데이터 접근(탐색, 업데이트): 제일 첫 번째 요소부터 순차적으로 연결된 노드를 탐색해 접근해야하기 때문에 O(N)
• 데이터 삽입:
  • 1) 추가하려는 데이터의 위치가 맨 앞인 경우: O(1)
  • 2) 추가하려는 데이터의 위치가 맨 앞 그 이후인 경우: O(N)
• 데이터 삭제:
  • 1) 삭제하려는 데이터의 위치가 맨 앞인 경우: O(1)
  • 2) 삭제하려는 데이터의 위치가 맨 앞 그 이후인 경우: O(N)

 

연결리스트의 사용 예시

연결리스트는 데이터의 추가, 삭제가 많이 일어나는 경우에 적합합니다. 예를 들어, 실시간으로 발생하는 로그 데이터를 저장할 때 많이 사용됩니다.

 

연결리스트의 대표적인 파이썬 문법

# 1) 데이터 조회
# indexing
L = [1, 2, 3, 4, 5] # list 자료형 데이터 생성
L[4] # 5
L[-1] # 5
L[-5] # 1

# slicing
L[0:3] # 첫 번째 원소부터 세 번째 원소까지 자르고 싶다. [1,2,3]
L[1:4] # 두 번째 원소부터 네 번째 원소까지 자르고 싶다. [2,3,4]


# 2) 데이터 삽입
L2 = []
# append: 리스트의 끝에 새로운 요소를 추가
L2.append(3)
L2.append(2)
L2.append(1)
print(L2) # [3, 2, 1]

#insert: 리스트의 특정 위치에 새로운 요소를 삽입
L2.insert(2, 'a')
L2.insert(2, 'b')
print(L2) # [3, 2, 'b', 'a', 1]


# 3) 데이터 삭제
# pop: 리스트 맨 마지막 요소를 삭제하고 그 값을 반환.
out = L2.pop() # 맨 마지막 원소가 빠짐. 1
out2 = L2.pop(2) # 'b'
print(out, L2) # 1 b [3, 2, 'a']

# remove: 리스트에서 특정 요소를 삭제
L2.remove(3)
print(L2) # [2, 'a']

 

---

3. 스택(Stack)

스택은 데이터를 저장하는 자료구조 중 가장 간단한 구조입니다. 스택은 데이터를 LIFO(Last-In-First-Out) 방식으로 저장하고, 가져올 때는 마지막에 저장한 데이터부터 가져옵니다. 스택은 배열이나 리스트를 통해 구현이 가능합니다. 파이썬에서는 list로 구현해야합니다. 

 

 

스택의 사용 예시

주로 함수 호출과 관련된 작업에서 많이 사용됩니다. 예를 들어, 컴퓨터 가상메모리의 스택영역에서 사용되는데, 함수가 호출되면서 다시 복귀할 주소를 저장하거나, 지역변수, 매개변수 등을 임시로 저장하는데에 쓰입니다. 또는 인터넷 상에서 앞으로가기 뒤로가기 버튼 기능도 스택구조로 만들어져있다고 볼 수 있습니다.

 

---

4. 큐(Queue)

큐는 데이터를 FIFO(First-In-First-Out) 방식으로 저장하고, 가져올 때는 먼저 저장한 데이터부터 가져옵니다. 즉, 가장 먼저 들어온 데이터가 가장 먼저 나가게 됩니다. 큐 또한 자료구조에서 가장 기본적인 구조 중 하나이며, 데이터를 순차적으로 처리할 때 많이 사용됩니다.

 

 

Queue의 사용 예시

작업 처리, 대기열 처리 등 데이터를 순차적으로 처리해야 하는 경우에 적합합니다. 예를 들어, 프린터에서 인쇄 대기열을 처리할 때 큐 자료구조를 사용할 수 있습니다.

 

 

 

여기까지 가장 기본이 되는 자료구조 중에 배열, 연결리스트, 스택, 큐에 대해서 알아보았습니다. 자료구조는 프로그램을 구현할 때 효율적인 알고리즘을 구현하기 위해 꼭 필요한 개념입니다. 적절한 자료구조를 선택하면 프로그램의 성능을 크게 향상시킬 수 있습니다. 또한, 자료구조는 컴퓨터과학 분야에서 널리 사용되는 개념이기 때문에, 이를 이해하고 숙지하는 것은 프로그래밍 능력을 향상시키는 데 매우 중요하니 꼭 자료구조 개념을 이해하시고 넘어가셨길 바랍니다!