[자료구조] LinkedList 링크드리스트

강의 복습+새로운 CV 수업진도+ 스터디까지 눈코 뜰새 없지만 놓칠 수 없는 자료구조 공부입니다.. 배열 포스팅을 간단하게 넘어간 느낌이 없지 않아서 링크드리스트는 열심히 해보는걸로..^^🔥

배열: 미리 연결된 공간을 예약해놓고 쓰는 구조
링크드리스트: 미리 예약할 필요 없이, 필요할 때마다 추가가 가능
위와 같이, 링크드리스트는 배열의 단점을 극복한 자료구조 입니다. 

1. 구조와 용어

▶ 노드: 데이터의 저장 단위, 데이터 + 포인터(다음 데이터를 가리키는 주소)로 구성
▶ 포인터: 각 노드 안에서 다음이나 이전의 노드와의 연결 정보를 가지고 있는 공간

출처:t.ly/pOtY

그림과 같이 링크드리스트의 특징은 데이터의 끝에서 다음 데이터를 가리키는 포인터가 존재한다는 점입니다. 
이를 가지고 있기 때문에 구조의 확장이 자유롭게 가능합니다. 

2. 구현

#객체지향 문법에 대한 이해가 필요합니다. 
class Node:
	def __init__(self,data): #class가 객체화 될때마다 Node를 만들어줌
		self.data = data
        self.next = None #주소 할당
#노드 구현
node1 = Node(1)
node2 = Node(2) #1과 2는 아직 연결되지 않음

node1.next = node2
head = node1 #head는 알고 있어야 합니다.

#데이터 추가하기
class Node:
	def __init__(self,data, next = None):
    self.data = dat
    self.next = next
def add(data):
	none = head
    while node.next: #추가하는 데이터는 맨 끝이 노드에 연결되어야함
    	node = node.next #while 구문이 반복됨
    #특정 노드의 주소가 없다 = 다음 노드가 없다 = 현재가 마지막 노드임
    node.next = Node(data) #마지막 노드의 주소에 입력한 데이터를 연결

3. 링크드리스트의 장점&단점

장점
▶ 미리 데이터 공간을 미리 할당하지 않아도 됨

단점
▶ 각 노드마다 다음 데이터를 가리킬 데이터 공간이 필요함 - 저장공간의 효율이 높지 않음
▶ 연결 정보를 찾는 시간이 필요해서 접근 속도가 느림
▶ 데이터를 중간 위치에 삽입 혹은 삭제할 때 데이터 간 연결을 재구성해야함 (부가적인 작업 필요)

단점 중 하나인 '중간 위치에 데이터 삽입 혹은 삭제'가 어려운 이유는 하나의 노드에 데이터 뿐만 아니라 다음 데이터와의 연결을 위한 주소 또한 구현되어있기 때문입니다.
 데이터의 삽입을 위해서는
① 삽입할 위치의 이전 데이터 주소(node.next)를 삽입하려는 데이터에 연결
② 삽입한 데이터의 주소를 삽입한 위치 다음 데이터에 연결
 데이터의 삭제를 위해서는
① 삭제할 위치의 이전 데이터(node) 주소를 삭제하려는 데이터 다음의 데이터(node.next.next)에 연결
② 연결이 끊긴 데이터 삭제
와 같은 작업이 필요합니다. 

데이터 추가 혹은 삭제를를 위한 구현도 약간 복잡하고 단점의 개수가 많아보이지만 장점이 굉장히 좋은 편인가 봅니다..!