배열 | 연결 리스트 | |
---|---|---|
k번째 원소의 접근 | O(1) | O(k) |
임의 위치에 원소 추가/제거 | O(N) | O(1) |
메모리상의 배치 | 연속 | 불연속 |
추가적으로 필요한 공간(Overhead) | - | O(N) |
연결 리스트는 컴퓨터과학에서 배열과 함께 가장 기본이 되는 대표적인 선형 자료구조 중 하나로 다양한 추상 자료형(ADT) 구현의 기반이 된다
동적으로 새로운 노드를 삽입하거나 삭제하기가 편하며, 연결구조를 통해 물리메모리를 연속적으로 사용하지 않아도 되기 때문에 관리도 쉽다. 또한, 데이터를 구조체로 묶어서 포인터로 연결한다는 개념은 여러가지 방법으로 다양하게 활용이 가능
탐색에는 O(n)소요, why ? -> 특정 인덱스에 접근하기 위해서는 전체를 순서대로 읽어야 함.
반면 시작 또는 끝 지점 추가,삭제,추출 O(1)에 가능
Array와 Trade Off 관계 (출처 : 생활코딩)
class Node:
def __init__(self, item):
self.val = item
self.next = None
class LinkedList:
def __init__(self, item):
self.head = Node(item)
# head는 초기 시작 노드를 말한다.
# 추가 메소드
def add(self, item):
cur = self.head
# cur는 현재 찍고 있는 노드를 의미한다. (포인터 개념)
while cur.next is not None:
cur = cur.next
cur.next = Node(item)
# 삭제 메소드
def remove(self, item):
if self.head.val == item:
self.head = self.head.next
else:
cur = self.head
while cur.next is not None:
if cur.val == item:
self.removeItem(item)
return
cur = cur.next
print("item does not exist in linked list")
def removeItem(self, item):
cur = self.head
while cur.next is not None:
if cur.next.val == item:
nextnode = cur.next.next
cur.next = nextnode
break
# 출력 메소드
def printlist(self):
cur = self.head
print("HEAD:: ", end='')
while cur is not None:
print(cur.val, '->', end=' ')
cur = cur.next
if cur is None:
print('empty')
# linked list size 출력 메소드
def size(self):
cur = self.head
count = 0
while cur:
count += 1
cur = cur.next
return count
# 탐색 메소드
def search(self, data):
check = self.head
for i in range(self.size()):
if check.val == data:
print(data, "The data is at the {} index.".format(i+1))
return None
check = check.next
print(data, "Data does not exist in linked list")
return None
linked = LinkedList(2)
linked.add(3)
linked.add(4)
linked.add(5)
linked.printlist()
linked.remove(3)
linked.printlist()
linked.search(5)
print(linked.size())
# HEAD:: 2 -> 3 -> 4 -> 5 -> empty
# HEAD:: 2 -> 4 -> 5 -> empty
# 5 The data is at the 3 index.
# 3