0. Intro
- 자료구조에서 꼭 알아야하는 연결리스트에 대해 알아보자.
- 해당 게시글에서는 단방향 연결리스트만 서술하고자 한다.
1. 리스트
- 리스트(list | 파이썬 내장 리스트와 다름)는 순서가 있는 데이터를 나열한 자료구조
- 실생활 예) 학생 명단, 상점의 판매 품목, 실시간 급상승 검색어...
2. 노드
- 연결리스트를 구성하는 각각의 원소
- 데이터와 포인터(reference)를 가진다.
2.1. 노드 클래스 구현
class Node:
def __init__(self,data=None,next = None):
self.data = data
self.next = next
#ex 1
n0 = Node('A')
n1 = Node('B')
n2 = Node('C')
n0.next = n1 # n0 뒤에 n1을 연결함
n1.next = n2 # n1 뒤에 n2를 연결함
print(n0.data)
print(n0.next.data)
print(n0.next.next.data)
----------------------------------------
A
B
C
#ex 2
n2 = Node('C')
n1 = Node('B',n2)
n0 = Node('A',n1)
print(n0.data)
print(n0.next.data)
print(n0.next.next.data)
_______________________________________________________________
A
B
C
3. 연결리스트(linked list)
- 리스트를 구현하는 방법중 하나
- 연결리스트는 각 노드가 데이터와 포인터를 가지고 한 줄로 연결되어 있는 방식으로 데이터를 저장하는 자료구조
3.1. 머리노드(head node)
- 연결리스트의 맨 앞에 있는 노드
3.2.꼬리노드(tail node)
- 연결리스트의 맨 끝에 있는 노드
4. 연결리스트 구현
class LinkedList:
def __init__(self):
self.no = 0
self.head = None
def __len__(self):
return self.no
4.1. add_first() 메소드 구현
def add_first(self,data):
ptr = self.head
self.head = Node(data,ptr)
self.no += 1
4.2. add_last() 메소드 구현
def add_last(self,data):
if self.head is None:
self.add_first(data)
else:
ptr = self.head
if ptr.next:
ptr= ptr.next
ptr.next = Node(data,ptr)
self.no += 1
4.3. print() 메소드 구현
def print(self):
ptr = self.head
while ptr:
print(ptr.data, end='')
if ptr.next:
print('->',end ='')
else:
print()
ptr = ptr.next
4.4. search() 메소드 구현
def search(self,data):
idx = 0
ptr = self.head
while ptr:
if ptr.data == data:
return idx
ptr = ptr.next
idx += 1
return -1
def __contains__(self,data):
return self.search(data) >= 0
4.5. remove_first() 메소드 구현
def remove_first(self):
if self.head:
self.head = self.head.next
self.no -= 1
4.6. remove_last() 메소드 구현
def remove_last(self):
if self.head:
if self.head.next is None:
self.remove_first()
else:
ptr = self.head
pre = self.head
while ptr.next:
pre = ptr
ptr = ptr.next
pre.next = None
self.no -= 1
4.7. clear() 메소드 구현
def clear(self):
while self.head:
self.remove_first()
self.no = 0
'CS Study > CLRS (자료구조 | 알고리즘)' 카테고리의 다른 글
[CLRS] [10-3] Queue(큐) (0) | 2024.11.04 |
---|---|
[CLRS] [10-2] Stack(스택) (1) | 2024.11.04 |
[CLRS] [9-1] Minimum and maximum(최솟값과 최댓값) (1) | 2024.11.04 |
[CLRS] [8-3] Bucket Sort(버킷 정렬) (0) | 2024.11.01 |
[CLRS] [8-2] Radix sort(기수 정렬) (0) | 2024.11.01 |