📌 연결 리스트란?
- 연결 리스트는 데이터 요소의 선형 집합으로. 데이터의 순서가 메모리에 물리적인 순서대로 저장되지 않는다.
- 배열(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 |