오늘의 강의 내용은 '연결 리스트'였다. 예전에 자료구조 공부한다고 깔짝였던 때에 연결리스트 강의를 들어놓은 적이 있어서 개념은 어렵지 않게 이해했는데 직접 구현하는 부분에서 애를 많이 먹었다. 여러가지 연결리스트 메소드를 직접 구현해보려고 했는데 실패하기도 했고, 몇가지 에러도 마주쳤다. 오늘의 TIL도 어제와 같이 강의 개념과 문제 정리를 하고 추가로 에러코드 트러블 슈팅도 해보자!
배열과 연결리스트
배열
여러 데이터를 저장하는 자료형 중에 가장 빨리 접근할 수 있는 자료구조
처음 생성 시 공간을 미리 할당해야하고, 생성 이후에는 크기 수정이 불가능하다.
처음에 공간을 정해두므로 데이터를 추가/삭제하는 과정이 쉽지 않다.
연결리스트(Linked List)
각 노드가 데이터와 포인터를 가지고 한 줄로 연결되어 있는 방식으로 데이터를 저장하는 자료구조
Node란?
출처 - 코드라떼 자바로 배우는 자료구조
프로그래밍 세게에서노드란 데이터 구조를 구성하는 각각의 개체를 말하며, 노드끼리는 서로 연결될 수도 있고, 그렇지 않을 수도 있다.
단일연결리스트
단일 연결 리스트는 각 노드에 자료 공간(데이터를 담는 공간)과 한 개의 포인터 공간(참조값을 담는 공간)이 있고, 각 노드의 포인터는 다음 노드를 가리킨다.
장단점
장점
저장되는 데이터의 개수가 에측 불가능 할 때 사용할 수 있다.
필요한 만큼만 메모리 공간을 사용하기 때문에 배열보다 상대적으로 메모리를 절약할 수 있다. 배열은 사용하지 않는 메모리 공간까지도 미리 계획해서 메모리를 할당해야하지만, 연결리스트는 데이터를 삽입할 때 노드를 생성하기 때문에 가변 배열처럼 사용할 수 있고 메모리를 상대적으로 절약할 수 있다.
데이터의 삽입/삭제가 빠르고 간단하다. 배열은 중간에 데이터가 삭제됐을 경우 재배치하는 시간이 데이터의 양과 삭제한느 데이터의 위치에 비례하기 때문에 빈번하게 삽입/삭제가 발생했을 때 많은 시간을 필요로 한다.
단점
하나의 연결만을 가지고 있기 때문에 노드를 찾을 때 앞에서부터 순차적으로 찾을 수 밖에 없으며, 인덱스를 계산하는 방식으로 접근하는 배열보다 탐색 속도가 느리다.
포인터는 항상 head(맨 앞)부터 시작해야하며, 노드 간 연결을 잘못했을 시에 다음 노드를 영원히 찾을 수 없다.
연결리스트 구현해보기
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
class LinkedList:
def __init__(self):
self.head = None
def append(self, val):
if not self.head:
self.head = ListNode(val, None)
return
node = self.head
while node.next:
node = node.next
node.next = ListNode(val, None)
파이썬의 __init__ 함수는 생성자이다. 생성자 관련 내용은 다음 글에서 정리해두었다.
