출처: 한빛출판네트워크
자료구조에는 선형 자료구조와 비선형 자료구조가 있으며 자료를 순차적으로 나열한 구조를 선형 자료구조라 말한다. 이번 글에서는 선형 자료구조 중 배열과, 링크드 리스트에 대해 공부해 보고자 한다.
1. 배열 (Array)
💡 배열의 개념
배열은 연속된 메모리 공간에 순차적으로 데이터를 저장한다.
배열은 선언할 때 크기를 저장하면 고정이 된다. 따라서 크기를 변경하고 싶다면 재선언을 해야 한다.
배열은 인덱스로 접근이 가능하며 인덱스는 0 부터 시작한다.
# 예시
array = [ '지수', '제니', '리사' , '로제']
for i in range(len(array)):
print(f'index {i} 번째는 {array[i]}입니다.')
출력값 :
index 0 번째는 지수입니다.
index 1 번째는 제니입니다.
index 2 번째는 리사입니다.
index 3 번째는 로제입니다.💡 배열의 시간 복잡도
| 연산 | 시간 복잡도 | 설명 |
|---|---|---|
| 접근 (Access) | O(1) | 인덱스를 사용해 특정 위치의 요소를 바로 참조 가능. |
| 탐색 (Search) | O(n) | 배열 전체를 순회해야 하므로, 최악의 경우 모든 요소를 확인해야 함. |
| 삽입 (Insert) | O(n) | 배열 중간에 삽입 시 나머지 요소를 이동해야 하기 때문에 최악의 경우 O(n). |
| 삭제 (Delete) | O(n) | 배열 중간에서 삭제 시 나머지 요소를 이동해야 함. |
| 추가 (Append) | O(1) | 배열 끝에 요소를 추가하는 경우(크기 조정이 필요하지 않다면) O(1). |
💡 배열의 장단점
1) 장점
- 탐색 시 접근이 O(1)로 빠르다.
2) 단점
- 크기 변경이 불가능해 메모리 낭비나 부족 현상이 일어날 수 있다.
- 삽입/삭제 시 많은 데이터 이동이 필요하다.
2. 연결 리스트 (Linked List)
💡 연결 리스트의 개념
출처: Find Todays Notes
연결 리스트는 노드가 포인터로 연결된 구조로, 데이터와 다음 노드의 주소를 저장한다.
쉽게 예시를 들자면 우리가 전국 여행을 할 때 지도에다가 방문할 도시를 선으로 연결한 것도 연결 리스트가 될 수 있다.
ex) 1일차 : 서울 -> 2일차 : 대전 -> 3일차 : 부산 -> 4일차 : 제주도
연결 리스트는 노드구조로 되어 있다. 노드(Node)는 데이터와 링크로 이루어져있다.
💡 단순 연결리스트
- 노드 정의
class Node():
def __init__(self):
self.data = None # 노드
self.link = None # 링크 - 데이터 삽입
def insertNode(findData, insertData):
global memory, head, current, pre
# case 1: head 앞에 삽입 (맨 앞에 삽입)
if head.data == findData:
node = Node()
node.data = insertData
node.link = head
head = node
return
#case 2: 중간에 삽입
current = head
while (current.link != None ):
pre = current
current = current.link
if (current.data == findData ) :
node = Node()
node.data = insertData
node.link = current
pre.link = node
return
#case 3: 찾는 데이터가 없을 때 = 마지막에 추가
node = Node()
node.data = insertData
current.link = node
return
- 데이터 삭제
def deleteNode(deleteData):
global memory, head, current, pre
#case1 : head를 삭제할 때
if (head.data == deleteData) :
current = head
head = head.link
del(current)
return
#case2 : 중간 데이터 삭제
current = head
while (current.link != None ):
pre = current
current = current.link
if (current.data == deleteData):
pre.link = current.link
del(current)
return
#case3 : 지울 데이터가 없을 때
return - 데이터 검색
def findNode(findData):
global memory, head, current, pre
current = head
if current.data == findData :
return current #노드 형태로 반환
while(current.link != None ):
current = current.link
if current.link == findData:
return current
return Node()
💡 연결리스트 시간복잡도
| 연산 | 시간 복잡도 | 설명 |
|---|---|---|
| 접근 (Access) | O(n) | 특정 인덱스로 직접 접근 불가, 첫 노드부터 순차 탐색 필요. |
| 탐색 (Search) | O(n) | 원하는 값을 찾기 위해 모든 노드를 순회해야 함. |
| 삽입 (Insert) | O(1) (노드 위치 알고 있을 때) / O(n) (탐색 포함) | 노드 위치를 알고 있다면 O(1), 중간 위치 삽입 시 탐색 필요하므로 O(n). |
| 삭제 (Delete) | O(1) (노드 위치 알고 있을 때) / O(n) (탐색 포함) | 노드 위치를 알고 있다면 O(1), 삭제할 노드를 찾기 위해 O(n) 탐색 필요. |
| 추가 (Append) | O(1) (단일 연결 리스트, 마지막 노드 포인터가 있을 경우) / O(n) | 마지막 노드에 접근해야 하므로 O(n), 포인터가 있다면 O(1). |
💡 연결리스트 장단점
1) 장점
- 크기 변경이 자유롭고, 삽입/삭제가 O(1)로 빠르다(노드를 직접 참조할 경우).
2) 단점
- 인덱스 접근이 O(n)으로 느리다.
- 추가 메모리(포인터) 사용으로 공간 낭비 가능하다.
Eunseo Park