연결리스트는 각 노드 들이 서로 연결을 통해 구현되어있는 형태의 리스트, 선형자료구조
Node 마디, 교점 Vertext 정점,꼭지점
Array List 와 다르게 하나의 데이터의 저장이 연속적인 메모리공에 늘어선것이 아니라
각 노드의 다음 주소값으로 서로 연결되어있다.
불연속적인 메모리공간에 흩뿌려진 형태
탐색 O(n)
배열과 달리 특정 인덱스에 접근하기위해서 전체를 순서대로 읽어 나가야한다
k 번째 노드에 접근하기 위해서 O(k)
삽입, 삭제 O(1)
시작지점 또는 끝지점에서 삽입 삭제는 상수시간에 가능하다
k번째 노드에서 삽입 삭제는 O(k) -> O(n)
장점
단점
python 으로 구현한 single linked list
python 은 list 가 기본적으로 linked list 를 지원한다
전체코드는 github 에 있습니다
# 데이터와 다음노드를 담고있는 노드 클래스
class Node:
def __init__(self, value):
self.value = value
self.next = None
class LinkedList:
def __init__(self):
self.head = None
self.length = 0
def add(self, index, val) -> None:
if self.length == 0 or index == 0:
self.add_front(val)
elif self.length <= index:
self.add_back(val)
else:
# index - 1 번째 노드까지 탐색후 새로운 노드 연결
cur = self.head
for _ in range(index - 1):
cur = cur.next
node = Node(val)
node.next, cur.next = cur.next, node
self.length += 1
# 마지막에 추가 O(n)
def add_back(self, val):
if self.length == 0:
self.head = Node(val)
else:
cur = self.move(self.length - 1)
cur.next = Node(val)
self.length += 1
def remove(self, index) -> None:
self.__check(index)
if index == 0:
self.head = self.head.next
else:
cur = self.move(index - 1)
cur.next = cur.next.next
self.length -= 1
# N 번 다음 노드로 진행
def move(self, index) -> Node:
self.__check(index)
cur = self.head
for _ in range(index):
cur = cur.next
return cur
def get(self, index) -> int:
return self.move(index).value
def print_all(self) -> None:
c = self.head
while c is not None:
print(c.value, end=', ')
c = c.next
print()
TEST 코드
# setup
li = LinkedList()
li.add_back(1)
li.add_back(2)
li.add_back(3)
li.print_all() # 1, 2, 3
li.add(1, 4) # index 1번에 노드 삽입
li.print_all() # 1, 4, 2, 3
print(li.size()) # size = 4
li.remove(2) # 2번 삭제
print(li.get(2)) # 2번 value=3
li.print_all() # 1, 4, 3