[ C.S 지식 정리 : 자료 구조 ] 배열(Array) & 연결-리스트(LinkedList)
∇ 자료 구조 : Array & LinkedList
목 차
1. 배열(Array)
2. 연결 - 리스트(Linked List)
3. 배열과 연결-리스트 비교
4. 코드 : 연결 리스트 순회/삽입/삭제 코드 구현
5. ++ 이중 연결 리스트 ( Double Linked List )
6. ++ 원형 연결 리스트 ( Circular Linked List )
Ⅰ. 배열 ( Array )
● '배열'은 입력된 데이터들이 메모리 공간에서 연속적으로 저장되어 있는 자료구조입니다.
● 메모리 상에서 연속적으로 저장되어 있는 특징을 가지기 때문에, index를 통한 접근이 용이.
● 배열의 크기는 처음 생성할 때 한번 정해지면, 이후에는 변경할 수 없습니다.
☆ 배열의 시간 복잡도.
● 탐색 시 : O(1) / 단, 접근하고자 하는 인덱스를 알고 있어야 합니다.
++ 순차적으로 탐색하는 경우 : O(n)
● 삽입 / 삭제
√ 배열의 처음 또는 중간에 삽입 및 삭제 : O(n)
- [삽입 지점 이후의 데이터들을 위치 조정해줘야 하기 때문에 ]
√ 배열의 끝에 삽입 및 삭제 : O(1)
Ⅱ. 연결 - 리스트 ( Linked - List )
● '연결-리스트'는 여러 개의 노드들이 '순차적으로 연결된 형태'를 가지는 자료구조이며,
첫번째 노드를 head, 마지막 노드를 tail 이라고 합니다.
● 각 노드(Node)는 데이터와 다음 차례 노드를 가리키는 '포인터'로 이루어져 있습니다.
● 배열과는 다르게 '메모리'를 연속적으로 사용하지 않습니다.
● 배열과는 다르게 순차적으로 접근해야 하는 면에서 불리할 수도 있으나,
노드가 연결된 구조이기 때문에 삽입-삭제에 용이합니다.
● Tree 구조의 근간이 되는 자료구조이며, Tree에서 사용되었을 때 그 유용성이 드러나게 됨, !
☆ 연결 리스트의 시간 복잡도.
● 탐색 시 : O(n)
● 삽입 / 삭제 : 삽입과 삭제 자체는 O(1) 입니다.
√ 연결 리스트의 처음에 삽입/삭제 : O(1)
√ 연결 리스트의 중반부에 삽입/삭제 : O(n) - '탐색 시간이 소요'
√ 연결 리스트의 끝에 삽입 / 삭제
- 끝을 가리키는 별도의 포인터를 가지는 경우 : O(1)
- 끝을 가리키는 별도의 포인터를 갖지 않는 경우 : O(n) - '탐색 시간 소요'
Ⅲ. 배열과 연결-리스트 비교.
☆ 장점.
◇ 배열 : 인덱스를 통한 빠른 접근 가능.
◆ 연결 리스트 : 삽입/삭제 용이.
☆ 단점.
◇ 배열
- 삽입/삭제가 오래 걸림.
- 배열 중간에 있는 데이터가 삭제되면, 공간 낭비가 발생함.
◆ 연결 리스트 : 임의 접근이 불가능하기 때문에, 무조건 처음부터 탐색을 진행해야 합니다.
☆ 용도.
◇ 배열 : 빠른 접근이 요구되면서, 데이터의 삽입과 삭제가 적을 때 !
◆ 연결 리스트 : 삽입과 삭제 연산이 잦고, 검색 빈도가 적을 때 !
Ⅳ. 예제 코드 : 연결 리스트 순회/삽입/삭제
class Node:
def __init__(self, item):
self.data = item
self.next = None
class LinkedList:
def __init__(self):
self.nodeCount = 0
self.head = None
self.tail = None
def getAt(self, pos):
if pos < 1 or pos > self.nodeCount:
return None
i = 1
curr = self.head
while i < pos:
curr = curr.next
i += 1
return curr
def insertAt(self, pos, newNode):
if pos < 1 or pos > self.nodeCount + 1:
return False
if pos == 1:
newNode.next = self.head
self.head = newNode
else:
if pos == self.nodeCount + 1:
prev = self.tail
else:
prev = self.getAt(pos - 1)
newNode.next = prev.next
prev.next = newNode
if pos == self.nodeCount + 1:
self.tail = newNode
self.nodeCount += 1
return True
def popAt(self, pos):
if pos < 1 or pos > self.nodeCount:
raise IndexError
node = self.getAt(pos)
if self.nodeCount == 1 & pos == 1:
self.head = None
self.tail = None
elif pos == 1:
self.head = self.getAt(pos+1)
else:
prev = self.getAt(pos-1)
if pos == self.nodeCount:
prev.next = None
self.tail = prev
else:
prev.next = prev.next.next
self.nodeCount -= 1
return node.data
def traverse(self):
result = []
curr = self.head
while curr is not None:
result.append(curr.data)
curr = curr.next
return result
Ⅴ. 이중 연결 리스트 ( Doubly Linked List )
● ' 이중 연결 리스트 ' 는 위에서 언급했던, 연결리스트와는 다르게
전/후로 탐색이 가능한 구조입니다.
● 즉, 단순 연결 리스트의 노드는 '해당 데이터와 다음 노드의 주소' 를 저장한다면,
이중 연결 리스트의 노드는 "해당 데이터, 이전 노드의 주소와 다음 노드의 주소" 를 모두 저장합니다
● 이중 연결 시트의 장점
- 단순 연결 리스트에서는 최악의 경우, N번의 탐색을 해야하지만(순차적으로 가기때문에)
이중 연결 리스트에서는 얻고자 하는 타겟 데이터의 위치가 tail(끝쪽)에 가깝다면
tail에서부터 역방향으로 탐색이 가능하기 때문에 탐색 시간을 줄일 수 있습니다.
ⅵ. 원형 연결 리스트 ( Cicular Linked List )
● ' 원형 연결 리스트 ' 는 단순 연결 리스트의 마지막 노드가
null을 가리키는 게 아닌, 처음 노드를 가리키는 구조입니다.
● head에서부터 데이터 순회를 반복적으로 진행하다보면, 다시 원점으로 돌아오는 구조입니다 !
● '이중 연결 리스트'도 마지막 노드가 처음 노드를 가리키는 구조가 되면,
이를 '이중 원형 연결 리스트' 라고 합니다.
'면접준비[프론트,백,데이터,CS] > CS 정리' 카테고리의 다른 글
| [ C.S 지식 정리 : 자료 구조 ] 자료구조 : 배열 (Array) (1) | 2024.12.13 |
|---|---|
| [ C.S 지식 정리 : 자료 구조 ] 자료구조 & 알고리즘의 정의. (1) | 2024.12.13 |
| [ C.S 지식 정리 : 자료 구조 ] 알고리즘 공부 하기 전 필요한, 자료구조 기초 지식들. (0) | 2024.11.16 |
| [ C.S 지식 정리 : 자료 구조 ] 자료구조와 알고리즘, '시간 복잡도' 에 대한 이해 (Big-O 표기법) (3) | 2024.11.02 |
| [ C.S 지식 정리 : 디자인 패턴 ] 디자인 패턴 : MVC 패턴이란? (1) | 2024.11.02 |