📖 연결 리스트(Linked list)

📌 연결 리스트란?

• 연결 리스트는 데이터 요소의 선형 집합으로. 데이터의 순서가 메모리에 물리적인 순서대로 저장되지 않는다.
• 배열(Array)과 함께 가장 기본이 되는 대표적인 선형 자료구조 중 하나로, 다양한 ADT 구현의 기반이 된다.
• 동적으로 새로운 노드를 삽입하거나 삭제하기 간편하며, 연결 구조를 통해 물리 메모리를 연속적으로 사용하지 않아도 되기 때문에 관리도 쉽다.
• 데이터를 구조체로 묶어 포인터로 연결한다는 개념은 여러 가지 방법으로 활용이 가능하다.

---

📌 배열과 연결 리스트의 차이

• 연결리스트는 배열과 다르게 엘리먼트와 엘리먼트 간의 연결(link)을 이용해서 리스트를 구현한 것을 의미한다. 그래서 Linked list에서 가장 중요한 것은 '연결이 무엇인가'를 파악하는 것이다.
  • 연결 리스트는 엘리먼트보단 node(마디, 교점) 혹은 vertex(정점, 꼭지점)라고 부른다.
• 연결 리스트는 배열과 달리 특정 인덱스에 접근하기 위해 전체를 순서대로 읽어야 하므로 상수 시간에 접근할 수 없다. 즉, 탐색에는 O(n)이 소요된다.
• 반면, 시작 또는 끝 지점에 아이템을 추가하거나 삭제, 추출하는 작업은 O(1)에 가능하다.

      출처: https://opentutorials.org/module/1335/8821

Linked list - Data Structure (자료구조)

---

📌 연결 리스트 구현(with Python)

• 연결 리스트: 각 node가 data와 pointer를 가지고 한 줄로 연결되어 있는 방식으로 데이터를 저장하는 자료 구조.
• node 구현

# 노드는 자료(data)와 다음 노드를 가리키는 참조값(next)로 구성되어 있다.
class ListNode:
	def __init__(self, data):
		self.data = data
		self.next = None​

• LinkedList Class 정의

# Node 클래스 정의
class Node:
	def __init__(self, data):
		self.data = data
		self.next = None

# LinkedList 클래스 정의
class LinkedList:

	# 초기화 메서드
	def __init__(self):
		# 초기 Node의 임의 데이터 - dummy
		dummy = Node("dummy")
		self.head = dummy
		self.tail = dummy
		self.current = None
		self.before = None
		self.num_of_data = 0

	# append 메서드
	# insert - 맨 뒤에 노드 추가, tail과 node의 next, 데이터 개수 변경
	def append(self, data):
		new_node = Node(data)
		self.tail.next = new_node
		self.tail = new_node
		self.num_of_data += 1

	# delete 메서드
	# delete - current 노드 삭제, 인접 노드의 current, next 변경, 데이터 개수 변경
	def delete(self):
		pop_data = self.current.data

		if self.current is self.tail:
			self.tail = self.before

		self.before.next = self.current.next
		# 중요: current가 next가 아닌 before로 변경된다.
		self.current = self.before

		self.num_of_data -= 1

		return pop_data

	# first 메서드
	# search1 - 맨 앞의 노드 검색, before, current 변경
	def first(self):
		# 데이터가 없는 경우 첫 번째 노드도 없기 때문에 None 리턴
		if self.num_of_data == 0:
			return None

		self.before = self.head
		self.current = self.head.next

		return self.current.data

	# next 메서드
	# search2 - current 노드의 다음 노드 검색, 이전의 first 메서드가 한 번은 실행 되어야 한다.
	def next(self):
		if self.current.next == None:
			return None

		self.before = self.current
		self.current = self.current.next

		return self.current.data

	def size(self):
		return self.num_of_data​

• LinkedList 클래스 내에는 node를 가리키는 4개의 참조와 데이터의 개수만 존재.
  • 4개의 참조 - head, before, current, tail
  • head: 맨 앞을 가리킴
  • before: 현재 위치 전
  • current: 현재 탐색 위치
  • tail: 맨 뒤
  • 데이터의 개수 - num_of_data
  • num_of_data: 데이터의 총 개수
  • 메서드 구현
    • 생성자: head, before, current, tail, num_of_data 초기화
    • .append(): 맨 뒤에 노드 추가(insert)
    • .first(): 맨 앞의 노드 검색(search)
    • .next(): 다음 노드 검색(search)
    • .delete(): 현재 노드 삭제(delete)

참고: https://wayhome25.github.io/cs/2017/04/17/cs-19/​

강의노트 18. 자료구조 - LinkedList (링크드 리스트) · 초보몽키의 개발공부로그

---

​