Notice
250x250
Recent Posts
Recent Comments
Link
넘치게 채우기
[자료구조] 1-4. 연결 리스트의 구현(Python) 본문
728x90
반응형
연결 리스트(Python) - 전체
|
class Node(): #노드 선언
def __init__(self, data, next = None):
self.data = data
self.next = next
class SimplyLinkedList():
def __init__(self):
self.head = None
def link(self, node, next): #노드 연결
node.next = next
def getTail(self): #꼬리 노드 불러오기
currentNode = self.head
while currentNode.next:
currentNode = currentNode.next
return currentNode
def getIndex(self, data): #data의 인덱스 반환
currentNode = self.head
index = 0
while currentNode.data != data:
currentNode = currentNode.next
index += 1
return index
def getNum(self, index): #index의 값 반환
currentNode = self.head
for i in range(index):
prevNode = currentNode
currentNode = currentNode.next
return currentNode.data
def append(self, data): #tail에 추가, 빈 리스트일경우, head에.
if self.head == None:
self.head = Node(data)
else:
tail = self.getTail()
tail.next = Node(data)
def appendhead(self, data): #head에 추가
self.head = Node(data, self.head)
def insertAt(self, data, index): #이 인덱스에 삽입
currentNode = self.head
for i in range(index):
prevNode = currentNode
currentNode = currentNode.next
prevNode.next = Node(data)
self.link(prevNode.next, currentNode)
def insertBeforeThisNumber(self, data, target_num): #이 번호 앞에 삽입
currentNode = self.head
while currentNode.data != target_num:
prevNode = currentNode
currentNode = currentNode.next
prevNode.next = Node(data)
self.link(prevNode.next, currentNode)
def insertAfterThisNumber(self, data, target_num): #이 번호 뒤에 삽입
currentNode = self.head
while currentNode.data != target_num:
prevNode = currentNode
currentNode = currentNode.next
prevNode = currentNode
currentNode = currentNode.next
prevNode.next = Node(data)
self.link(prevNode.next, currentNode)
def pop(self): #맨 끝 삭제
currentNode = self.head
while currentNode.next:
prevNode = currentNode
currentNode = currentNode.next
prevNode.next = None
def pophead(self): #맨 앞 삭제
headNode = self.head
self.head = self.head.next
headNode.next = None
def popAt(self, index): #특정 인덱스 pop
currentNode = self.head
for i in range(index):
prevNode = currentNode
currentNode = currentNode.next
if currentNode.next:
self.link(prevNode, currentNode.next)
currentNode = None
def popIt(self, data): #특정 값 pop
currentNode = self.head
while currentNode.data != data:
prevNode = currentNode
currentNode = currentNode.next
prevNode = currentNode
currentNode = currentNode.next
if currentNode.data == data:
self.link(prevNode, currentNode.next)
def printList(self): #프린트
currentNode = self.head
while currentNode.next:
print(currentNode.data)
currentNode = currentNode.next
print(currentNode.data)
def listMerge(self, nextList): #리스트 병합
tail = self.getTail()
self.link(tail, nextList.head)
|
cs |
노드의 선언
Node클래스를 선언한다. 입력값이 아무것도 없을 때, 다음 포인터값은 None이다.
|
1
2
3
4
|
class Node(): #노드 선언
def __init__(self, data, next = None):
self.data = data
self.next = next
|
cs |
연결 리스트의 선언
연결 리스트 클래스를 선언한다. 초기에 head노드는 None으로 지정된다.
|
1
2
3
|
class SimplyLinkedList():
def __init__(self):
self.head = None
|
cs |
노드 연결
연결 리스트의 노드의 포인터를 지정한다.
|
1
2
|
def link(self, node, next): #노드 연결
node.next = next
|
cs |
꼬리 노드 불러오기
연결 리스트의 맨 마지막 노드를 가져온다.
Head부터 리스트의 끝까지 탐색한 후, 그 마지막 노드를 반환한다
|
1
2
3
4
5
|
def getTail(self): #꼬리 노드 불러오기
currentNode = self.head
while currentNode.next:
currentNode = currentNode.next
return currentNode
|
cs |
연결 리스트에서 특정 값의 인덱스 찾기
처음부터 탐색하면서, 특정 값을 찾으면, 인덱스를 반환한다.
|
1
2
3
4
5
6
7
|
def getIndex(self, data): #data의 인덱스 반환
currentNode = self.head
index = 0
while currentNode.data != data:
currentNode = currentNode.next
index += 1
return index
|
cs |
연결 리스트에서 특정 인덱스의 값 찾기
처음에서 인덱스만큼 이동한 뒤, 해당 노드의 값을 반환한다.
|
1
2
3
4
5
6
|
def getNum(self, index): #index의 노드값 반환
currentNode = self.head
for i in range(index):
prevNode = currentNode
currentNode = currentNode.next
return currentNode.data
|
cs |
연결 리스트의 노드 추가
첫 노드가 빈 노드이면, head 노드에 추가한다.
리스트에 노드가 하나라도 있으면, tail 뒤에 추가해준다.
|
1
2
3
4
5
6
|
def append(self, data): #tail에 추가, 빈 리스트일경우, head에.
if self.head == None:
self.head = Node(data)
else:
tail = self.getTail()
tail.next = Node(data)
|
cs |
연결 리스트의 head에 노드 추가
기존에 head가 있는 연결 리스트에 새로운 head노드를 생성한다.(빈 노드에서는 오류 발생)
새로운 head의 next = 기존의 head
|
1
2
|
def appendhead(self, data): #head에 추가
self.head = Node(data, self.head)
|
cs |
특정 인덱스에 삽입
값과 인덱스를 입력받아서 그 인덱스에 넣는다. 기존 데이터들은 한칸씩 밀려난다.
(기존 인덱스 전 노드) - (새로운 노드) - (기존 인덱스의 노드)
|
1
2
3
4
5
6
7
|
def insertAt(self, data, index): #이 인덱스에 삽입
currentNode = self.head
for i in range(index):
prevNode = currentNode
currentNode = currentNode.next
prevNode.next = Node(data)
self.link(prevNode.next, currentNode)
|
cs |
이 숫자 전/후에 삽입
값과 특정 값을 받아서 특정 값의 전/후에 삽입시킨다.
앞:
(특정 값 이전 노드) - (새로운 노드) - (특정 값을 가진 노드)
|
1
2
3
4
5
6
7
|
def insertBeforeThisNumber(self, data, target_num): #이 번호 앞에 삽입
currentNode = self.head
while currentNode.data != target_num:
prevNode = currentNode
currentNode = currentNode.next
prevNode.next = Node(data)
self.link(prevNode.next, currentNode)
|
cs |
뒤:
(특정 값을 가진 노드) - (새로운 노드) - (특정 값을 가진 노드의 다음 노드)
|
1
2
3
4
5
6
7
8
9
|
def insertAfterThisNumber(self, data, target_num): #이 번호 뒤에 삽입
currentNode = self.head
while currentNode.data != target_num:
prevNode = currentNode
currentNode = currentNode.next
prevNode = currentNode
currentNode = currentNode.next
prevNode.next = Node(data)
self.link(prevNode.next, currentNode)
|
cs |
노드 삭제
맨 뒤의 노드를 없앤다. 맨 끝 노드의 이전 노드에서 다음을 None을 향하게한다.
|
1
2
3
4
5
6
|
def pop(self): #맨 끝 삭제
currentNode = self.head
while currentNode.next:
prevNode = currentNode
currentNode = currentNode.next
prevNode.next = None
|
cs |
맨 앞의 노드 삭제
head노드를 없앤다. 기존 head의 다음 노드를 새로운 head로 한다.
|
1
2
3
4
|
def pophead(self): #맨 앞 삭제
headNode = self.head
self.head = self.head.next
headNode.next = None
|
cs |
특정 위치에 있는 노드 삭제
입력받은 인덱스의 값을 없앤다.
(입력받은 인덱스 전 노드) - (입력받은 인덱스 다음 노드) 연결을 시켜준다.
|
1
2
3
4
5
6
7
8
|
def popAt(self, index): #특정 인덱스 pop
currentNode = self.head
for i in range(index):
prevNode = currentNode
currentNode = currentNode.next
if currentNode.next:
self.link(prevNode, currentNode.next)
currentNode = None
|
cs |
특정 값을 가진 노드 삭제
입력받은 값을 가진 노드를 없앤다.
(특정 값 노드 이전의 노드) - (특정 값 노드 다음 노드) 연결을 시켜준다.
|
1
2
3
4
5
6
7
8
9
|
def popIt(self, data): #특정 값 pop
currentNode = self.head
while currentNode.data != data:
prevNode = currentNode
currentNode = currentNode.next
prevNode = currentNode
currentNode = currentNode.next
if currentNode.data == data:
self.link(prevNode, currentNode.next)
|
cs |
연결 리스트 출력
head부터 tail까지 출력시킨다.
|
1
2
3
4
5
6
|
def printList(self): #프린트
currentNode = self.head
while currentNode.next:
print(currentNode.data)
currentNode = currentNode.next
print(currentNode.data)
|
cs |
연결 리스트 합치기
두 연결 리스트를 합친다. 리스트의 tail을 nextList에 들어가는 연결 리스트의 head에 연결시킨다.
|
1
2
3
|
def listMerge(self, nextList): #리스트 병합
tail = self.getTail()
self.link(tail, nextList.head)
|
cs |
예시
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
|
node1 = Node(7) #7을 가진 노드 생성
node2 = Node(3) #3을 가진 노드 생성
List1 = SimplyLinkedList() #리스트1 생성
List2 = SimplyLinkedList() #리스트2 생성
List1.head = node1 #리스트1의 head를 node1로 설정
List1.link(node1, node2) #node1의 다음 노드를 node2로 지정
List2.append(4) #리스트2에 4를 가진 노드 추가
List1.appendhead(780) #리스트1의 head를 780을 가진 노드로 설정
List2.insertAfterThisNumber(60, 4) #리스트2의 4 뒤에 60 삽입
List1.insertAt(68, 1) #List1의 1인덱스자리에 68을 가진 노드 넣기(기존 값들은 밀려남)
List2.append(200) #리스트2의 맨 끝에 200을 가진 노드 추가
List2.popAt(1) #리스트2의 1인덱스자리의 노드(60을 가진 노드) 제거
List1.listMerge(List2)#리스트1 - 리스트2 합치기(연결)
List1.printList() #리스트1 출력
|
cs |
|
1
2
3
4
5
6
|
780
68
7
3
4
200
|
cs |
728x90
반응형
'컴퓨터과학 > 자료구조' 카테고리의 다른 글
| [자료구조] 2-2. 큐(Queue) (0) | 2022.10.13 |
|---|---|
| [자료구조] 2-1. 스택(Stack) (0) | 2022.10.06 |
| [자료구조] 1-3. 이중 연결리스트, 원형 연결 리스트(Doubly Linked List, Circular Linked List) (0) | 2022.09.07 |
| [자료구조] 1-2. 연결 리스트(Linked List) (0) | 2022.09.06 |
| [자료구조] 1-1. 배열, 순차 리스트(Array, Sequential List) (0) | 2022.09.03 |
'컴퓨터과학/자료구조' Related Articles
more
