1. 📌 연결 리스트란?
- 연결 리스트는 데이터 요소의 선형 집합으로. 데이터의 순서가 메모리에 물리적인 순서대로 저장되지 않는다.
- 배열(Array)과 함께 가장 기본이 되는 대표적인 선형 자료구조 중 하나로, 다양한 ADT 구현의 기반이 된다.
- 동적으로 새로운 노드를 삽입하거나 삭제하기 간편하며, 연결 구조를 통해 물리 메모리를 연속적으로 사용하지 않아도 되기 때문에 관리도 쉽다.
- 데이터를 구조체로 묶어 포인터로 연결한다는 개념은 여러 가지 방법으로 활용이 가능하다.
2. 📌 배열과 연결 리스트의 차이
- 연결리스트는 배열과 다르게 엘리먼트와 엘리먼트 간의 연결(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
3. 📌 연결 리스트 구현(with Python)
- 연결 리스트: 각 node가 data와 pointer를 가지고 한 줄로 연결되어 있는 방식으로 데이터를 저장하는 자료 구조.
- node 구현
<python /># 노드는 자료(data)와 다음 노드를 가리키는 참조값(next)로 구성되어 있다. class ListNode: def __init__(self, data): self.data = data self.next = None
- LinkedList Class 정의
<python /># 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 |