[자료 구조] 배열 & 연결 리스트 (Array & LinkedList)
배열 (Array)
- 배열은 입력된 데이터들이 메모리 공간에서 연속적으로 저장되어 있는 자료구조이다.
- 메모리 상에서 연속적으로 저장되어 있는 특징을 갖기 째문에, index를 통한 접근이 용이하다.
- 배열의 크기는 처음 생성할 때 정하며 이후에는 변경할 수 없다.
시간 복잡도
- 탐색 : O(1). 단, 접근하고자 하는 인덱스를 알고 있어야 한다. 순차적으로 탐색시에는 O(n).
- 삽입 / 삭제 :
- 배열의 처음 또는 중간에 삽입 및 삭제 : O(n)
(삽입 지점 이후의 데이터를 옮겨야 하기 때문.) - 배열의 끝에 삽입 및 삭제 : O(1)
- 배열의 처음 또는 중간에 삽입 및 삭제 : O(n)
연결 리스트 (Linked List)
- 연결 리스트는 여러 개의 노드들이 순차적으로 연결된 형태를 갖는 자료구조이며, 첫번째 노드를 head, 마지막 노드를 tail이라고 한다.
- 각 노드는 데이터와 다음 노드를 가리키는 포인터로 이루어져 있다.
- 배열과는 다르게 메모리를 연속적으로 사용하지 않는다.
- 배열과는 다르게 순차적으로 접근해야 하는 면에서 불리할 수도 있으나, 노드가 연결된 구조이기 때문에 삽입, 삭제에 용이하다.
- 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에서부터 역방향으로 탐색이 가능하기 때문에 탐색 시간을 줄일 수 있다.
원형 연결 리스트 (Circular Linked List)
-
원형 연결 리스트는 단순 연결 리스트의 마지막 노드가 null을 가리키는 게 아닌, 처음 노드를 가리키는 구조이다.
-
즉, head에서부터 순회를 반복적으로 진행하다보면 다시 처음으로 돌아오는 구조이다.
-
이중 연결 리스트도 마지막 노드가 처음 노드를 가리키는 구조가 되면, 이를 이중 원형 연결 리스트라고 한다.
Reference
배열과 연결리스트 (Array & LinkedList) - AndroidTeacher
Author And Source
이 문제에 관하여([자료 구조] 배열 & 연결 리스트 (Array & LinkedList)), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@xxhaileypark/자료-구조-배열-연결-리스트-Array-LinkedList저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)