Notice
Recent Posts
Recent Comments
Link
일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | 2 | 3 | ||||
4 | 5 | 6 | 7 | 8 | 9 | 10 |
11 | 12 | 13 | 14 | 15 | 16 | 17 |
18 | 19 | 20 | 21 | 22 | 23 | 24 |
25 | 26 | 27 | 28 | 29 | 30 | 31 |
Tags
- 알고리즘
- 코딩테스트
- 파이썬
- 그리디
- BFS
- 반복문
- 정렬
- DFS
- 자료구조
- 다이나믹프로그래밍
- solvedac
- 프로그래머스
- 데이터마이닝
- 큐
- 그래프
- Datastructure
- DP알고리즘
- dp
- greedy
- 그래프탐색
- 그리디알고리즘
- 문제풀이
- 문자열
- 백준
- 수학
- PYTHON
- Baekjoon
- 너비우선탐색
- 코테
- 깊이우선탐색
Archives
- Today
- Total
nyunu
[자료구조] 단일 연결 리스트 구현 (in python) 본문
728x90
강의 출처) 숙명여자대학교 소프트웨어융합전공 강의 "자료구조", 이현자 교수님
연결리스트의 기본 구조
- 데이터 필드와 하나 이상의 링크 필드로 구성된 노드가 연결된 형태
=> 노드 = 데이터 필드(해당 노드가 담고있는 data) + 링크 필드(다음 노드를 가리키는 link)
단일 연결 리스트
1. 단일 연결 리스트란 ?
- 노드들이 한 방향으로 연달아 연결되어 있는 구조
- head, tail 노드
- head : 리스트의 첫 노드
- tail : 리스트의 끝 노드
2. 단일 연결 리스트 구현
1) 노드 기본 구현
class Node:
def __init__(self, item):
self.data = item
self.link = None
2) 단일 연결 리스트 연산 종류
- 삽입 연산
- 삭제 연산
- 리스트 길이 계산
- 리스트 연결
- 역 리스트
3) 단일 연결 리스트 연산 구현
(1) 삽입 연산
- 두 가지 단계로 분류 가능
- Step 1
: 삽입될 노드의 앞 노드의 data값을 전달받으면 앞 노드를 찾아 노드가 어디에 삽입되어야 할지 탐색 - Step 2
: 위에서 찾은 노드가 삽입되어야 할 위치에 노드를 삽입- 삽입할 때 고려할 경우의 수
- 아예 빈리스트인 경우
- 앞 노드가 지정된 경우 (def insert에서 prev_data에 값이 할당된 경우)
- 앞 노드가 None인 경우 (def insert에서 prev_data에 값이 할당되지 않은 경우 = 앞에 연결할 노드가 없다는 의미 = 맨 앞에 노드 추가 != 빈리스트)
- 삽입할 때 고려할 경우의 수
- Step 1
- 코드 구현
- Step 1 & 2
def find(self, item): # STEP 1
# item : insert시에 삽입하는 리스트의 앞 노드 정보 (link말고 data로 줌)
if not self.head: return None, None
# self.head가 없다 -> 빈리스트이니까 none, none 반환
# 위의 if문을 충족하지 않으면 아래 코드를 실행
temp = self.head
# self.head의 객체를 temp에 할당
prev = None
# prev = None으로 정의하고
while temp:
if temp.data == item:
# temp.data가 item과 동일하면 그때의 temp 객체가 삽입 노드의 앞 노드인 것
return prev, temp
# temp의 앞노드인 prev, 그리고 삽입 노드의 앞 노드인 temp를 반환 => prev -> temp 이렇게 연결되어 있는 것
prev = temp
# temp를 prev에 할당하고
temp = temp.link
# 다음 리스트를 가리키는 temp.link를 temp로 할당
return None, None
# 만약에 while문이 리스트가 tail에 이를때까지 돌아갔는데도 return값이 없었다
# -> 앞 노드에 해당하는 것이 리스트에 없다는 의미이므로 None, None을 반환
def insert(self, prev_data, item): # STEP 2
if self.head is None:
# 공백리스트이면 당연히 head도 없고, tail도 없으니 -> 새로운 데이터가 포함되면 head = tail 성립
node = Node(item)
# 삽입할 데이터를 담은 리스트를 생성하고 (Node라는 클래스를 사용하여 만든 객체)
self.head = node
# self.head도 위에서 정의한 node 객체를 담고
self.tail = node
# self.tail도 위에서 정의한 node 객체를 담음
return
node = Node(item)
# self.head가 비어있지 않아도 node 객체 생성해야하니까
# -> node = 삽입할 데이터의 값을 담은 노드니까 삽입노드
if prev_data is None:
# 입력받은 prev_data의 값이 None이면 리스트의 맨 앞에 노드를 삽입한다는 의미
# -> prev_data는 지금 삽입하는 연결리스트의 앞노드의 데이터값이 이거다를 지정해준 것
# -> prev_data = None이다 ? = 삽입할 노드 앞의 노드가 없다 = 리스트 젤 앞에 삽입하는거다
node.link = self.head
# self.head에 할당되어 있는 객체를 node의 link에 할당 (self.head를 node의 뒤로 연결시키는 것)
self.head = node
# 그리고 node 객체를 self.head에 할당해서 node를 headnode가 되도록 함
return
pprev, prev = self.find(prev_data)
# 앞서 find함수에서 찾고 반환한 결과를 pprev, prev값으로 받음
# : pprev -> prev -> node 순으로 연결될 예정
if prev is None:
# 근데 이렇게 했는데 만약에 이전 노드가 없었다하면
print("Not Exist previous node")
# 존재하지 않는다고 print
return
else:
# 아니면 = 이전 노드가 있었다면
node.link = prev.link
# 원래 prev가 가리키고 있던 리스트의 link를 node에게 연결
prev.link = node
# node를 prev.link에 연결
if node.link is None: self.tail = node
# 만약에 node에 링크가 할당되어 있지 않다
= prev가 tail이었어서 할당해줄 link가 없었던 것
-> 그러니까 이제는 node가 tail이 됨
(2) 삭제 연산
- 삭제할 때 고려할 경우의 수
- 앞노드가 None이 아닌 경우 (삭제할 노드의 앞 노드가 주어진 경우)
- 앞노드가 None인 경우 (가장 앞의 노드를 삭제할 경우)
- 코드 구현
def delete(self,item):
if self.head is None:
# 빈리스트이면
print("Empty List")
return
prev, node = self.find(item)
# 삭제할 데이터의 노드를 찾음
-> node가 삭제할 데이터의 노드, prev는 삭제할 데이터 이전의 노드
if node is None:
# 찾아봤는데 삭제할 데이터의 노드가 존재하지 않으면 삭제할 것도 없지
print("Not Exist node")
return
if prev:
# prev가 존재하면
prev.link = node.link
# node가 연결하고 있는 다음 리스트를 prev.link에 할당해주고 node는 그 연결에서 빠져나옴
print("Delete complitely")
else:
# prev가 존재하지 않으면
if self.head == node:
# 그리고 node가 head이면
print("Head deleted")
self.head = node.link
# 노드가 연결하고 있던 다음 리스트를 헤드로 지정하고 node는 그 연결에서 빠져나옴
if node == self.tail: self.tail = prev
# node가 tail이었으면 prev를 tail로 지정
del node
# 마지막으로는 node라는 리스트 삭제
(3) 리스트 길이 계산
- 기본 원리 : head에 연결된 노드부터 시작해서 link를 통해 하나씩 넘어가면서 count를 +1
- 코드 구현
def length_list(self):
count = 0
temp = self.head
while temp:
count += 1
temp = temp.link
return count
(4) 리스트 연결
- 리스트 연결 경우의 수
- 첫번째 리스트가 빈리스트이면 -> 두번째 리스트가 결과가 됨
- 첫번째 리스트가 빈리스트가 아니면 -> 첫번째 리스트의 tail에 두번째 노드 head를 저장
- 코드 구현
def concat(self, second):
if self.head is None:
# 첫번째 리스트가 빈리스트인 경우
return second
elif second:
# second가 빈리스트가 0이 아닌 경우
temp = self.head
# 첫번째 리스트의 self.head를 temp에 할당
while temp.link:
temp = temp.link
# temp에 temp.link를 할당하면서 계속 다음 리스트로 넘어가다가 더이상 link값이 할당되지 않으면 stop
-> 첫번째 리스트의 tail에 닿으면 stop
temp.link = second
# 연결할 second 리스트를 첫번째 리스트 tail의 링크에 할당
while seconde.link:
second = second.link
# second 리스트를 대상으로 위의 과정 반복해서 second 리스트의 tail에 닿으면 stop
self.tail = second
# second의 tail을 전체 리스트의 tail에 할당
return self.head
(5) 역리스트
- 기본 원리
- 코드 구현
def reverse(self):
one = self.head
two = three = None
self.tail = self.head # 역리스트를 만드는 과정이니까 head를 tail로
while one:
three = two
two = one
# 연결리스트에 할당되면 three - two - one 이렇게 할당됨
= three가 셋 중 가장 앞 노드에 위치하고 one은 셋 중 가장 뒷 노드에 위치함
one = one.link
# one은 그 다음 노드로 넘어가고
two.link = three
# three를 two의 link에 할당
= 원래 연결 리스트에서 two는 three보다 뒤에 위치
-> 뒷 리스트의 링크에 앞 노드를 연결해주어 역순이 되도록 하는 것
self.head = two
# one이 None이다
= 원래 리스트의 tail을 읽은 후 그 다음 노드를 읽지 못했다
= two가 원래 연결리스트의 tail에 위치했을 때 while문 break
-> 그래서 two가 head
(6) 전체 코드
class Node:
def __init__(self, item):
self.data = item
self.link = None
class SinglyLinkedlist:
def __init__(self):
self.head = None
self.tail = None
def view(self):
temp = self.head
# temp라는 변수에 self.head(Node 클래스를 이용하여 생성한 객체
+ 근데 비어있는게 아니라 앞선 내용이 포함되어 있음)라는 객체를 할당
print('[', end = ' ')
while temp:
# 아래의 과정을 반복하다가 temp.link가 None일 때
= self.tail에 도달해 더이상의 link가 존재하지 않을 때 STOP
print(temp.data, end = ' ')
# 가장 먼저는 self.head에 있는 데이터를 읽어오고 그 이후에 연결되어 있는 리스트들의 값을
연결된 순서대로 읽어옴 -> 어떻게 ?는 아래줄에
temp = temp.link
# temp.link라는 변수는 다음에 연결되어 있는 Node라는 클래스를 이용하여 만든 객체를 참조하고 있음
-> 다음 리스트를 불러옴
print(']', end= ' ')
if self.head:
# self.head 있으면 빈 리스트 아니니까 출력
print('H = ', self.head.data, "T = ", self.tail.data)
else:
print("Empty list")
def isEmpty(self):
return not self.head
def insert(self, prev_data, item): # 데이터 삽입
if self.head is None:
node = Node(item)
self.head = node
self.tail = node
return
node = Node(item)
if prev_data is None:
node.link = self.head
self.head = node
return
pprev, prev = self.find(prev_data)
print("Not Exist previous node")
return
else:
node.link = prev.link
prev.link = node
if node.link is None: self.tail = node
def delete(self,item): # 데이터 삭제
if self.head is None:
print("Empty List")
return
prev, node = self.find(item)
if node is None:
print("Not Exist node")
return
if prev:
prev.link = node.link
print("Delete complitely")
else:
if self.head == node:
print("Head deleted")
self.head = node.link
if node == self.tail: self.tail = prev
del node
def find(self, item): # 노드 찾기
if not self.head: return None, None
temp = self.head
prev = None
while temp:
if temp.data == item:
return prev, temp
prev = temp
temp = temp.link
return None, None
def length_list(self): # 길이 계산
count = 0
temp = self.head
while temp:
count += 1
temp = temp.link
return count
def concat(self, second): # 리스트 연결
if self.head is None:
return second
elif second:
temp = self.head
while temp.link:
temp = temp.link
temp.link = second
while seconde.link:
second = second.link
self.tail = second
return self.head
def reverse(self): # 역 리스트
one = self.head
two = three = None
self.tail = self.head
while one:
three = two
two = one
one = one.link
two.link = three
self.head = two
728x90
'Data Structure & Algorithm' 카테고리의 다른 글
[자료구조] 이진트리 표현법 (in python) (1) | 2023.06.18 |
---|---|
[자료구조] 이진트리 정의 (in python) (1) | 2023.06.18 |
[자료구조] 원형 리스트, 이중 리스트 구현 (in python) (1) | 2023.06.18 |
[자료구조] 수식 평가_중위, 후위, 전위 (in python) (0) | 2023.06.18 |
[자료구조] 스택, 큐, 원형 리스트 (in python) (1) | 2023.06.18 |