기록하는 습관

📌 연결 리스트란?

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

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

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

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

 

Linked list - Data Structure (자료구조)

소개 Linked List는 Array List와는 다르게 엘리먼트와 엘리먼트 간의 연결(link)을 이용해서 리스트를 구현한 것을 의미합니다. 그래서 이름도 linked list입니다. 그렇게 보면 linked list에서 가장 중요한

opentutorials.org


📌 연결 리스트 구현(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 (링크드 리스트) · 초보몽키의 개발공부로그

패스트캠퍼스 컴퓨터공학 입문 수업을 듣고 중요한 내용을 정리했습니다. 개인공부 후 자료를 남기기 위한 목적임으로 내용 상에 오류가 있을 수 있습니다.

wayhome25.github.io


'Computer Science > Data Structure' 카테고리의 다른 글

Queue와 Priority Queue란?  (0) 2023.01.24
이진 검색 트리(BST)란?  (0) 2023.01.24
해시 테이블(Hash Table)이란?  (0) 2023.01.13
profile

기록하는 습관

@honeybee9999

포스팅이 좋았다면 "좋아요❤️" 또는 "구독👍🏻" 해주세요!