파이썬/자료구조와 알고리즘
단순 연결 리스트 복습
sck07013
2024. 8. 27. 23:44
단순 연결 리스트의 개념
구조
원리
노드 구조
다음 데이터를 가리키는 링크(link)가 필요
데이터 뿐만 아니라 링크도 저장 해야함
데이터와 링크로 구성된 항목을 노드라 명명
head
첫번째 노드를 head 라고 함
#노드 생성
class Node() : #Node 라는 데이터 형을 만드는 것
def __init__ (self) : #데이터 형을 생성 할 때 자동으로 실행되는 부분
self.data = None #데이터가 저장되는 부분
self.link = None #링크가 저장되는 부분
#첫번째 노드 생성
class Node() :
def __init__ (self) :
self.data = None
self.link = None
node1 = Node()
node1.data = '다현'
print(node1.data, end = ' ')다현
#노드 연결
class Node() :
def __init__ (self) :
self.data = None
self.link = None
node1 = Node() #첫번째 노드 생성
node1.data = '다현' #데이터에 다현 입력
node2 = Node() #두번째 노드 생성
node2.data = '정연' #데이터에 정연 입력
node1.link = node2 #첫번째 노드의 링크에 두번째 노드 연결
node3 = Node()
node3.data = '쯔위'
node2.link = node3
node4 = Node()
node4.data = '사나'
node3.link = node4
node5 = Node()
node5.data = '지효'
node4.link = node5
print(node1.data, end = ' ') #첫번째 노드의 데이터 출력
print(node1.link.data, end = ' ') #첫번째 노드의 다음 데이터 출력
print(node1.link.link.data, end = ' ') #첫번째 노드의 다음 다음 데이터 출력
print(node1.link.link.link.data, end = ' ') #첫번째 노드의 다음 다음 다음 데이터 출력
print(node1.link.link.link.link.data, end = ' ') #첫번째 노드의 다음 다음 다음 다음 데이터 출력다현 정연 쯔위 사나 지효
#노드 연결 개선
class Node() :
def __init__ (self) :
self.data = None
self.link = None
node1 = Node() #첫번째 노드 생성
node1.data = '다현' #데이터에 다현 입력
node2 = Node() #두번째 노드 생성
node2.data = '정연' #데이터에 정연 입력
node1.link = node2 #첫번째 노드의 링크에 두번째 노드 연결
node3 = Node()
node3.data = '쯔위'
node2.link = node3
node4 = Node()
node4.data = '사나'
node3.link = node4
node5 = Node()
node5.data = '지효'
node4.link = node5
current = node1 #첫번째 노드를 현재 노드로 설정
print(current.data, end = ' ') #첫번째 노드의 데이터 출력
while current.link != None : #현재 링크가 비어있지 않는 동안 반복
current = current.link #반복 된다면 current.link.link ... 이런식으로 진행
print(current.data, end = ' ') #현재 노드의 데이터 출력다현 정연 쯔위 사나 지효
#노드 삽입
class Node() :
def __init__ (self) :
self.data = None
self.link = None
node1 = Node() #첫번째 노드 생성
node1.data = '다현' #데이터에 다현 입력
node2 = Node() #두번째 노드 생성
node2.data = '정연' #데이터에 정연 입력
node1.link = node2 #첫번째 노드의 링크에 두번째 노드 연결
node3 = Node()
node3.data = '쯔위'
node2.link = node3
node4 = Node()
node4.data = '사나'
node3.link = node4
node5 = Node()
node5.data = '지효'
node4.link = node5
newNode = Node()
newNode.data = '지원'
newNode.link = node2.link #새 노드에 두번째 노드의 링크를 복사
node2.link = newNode #두번째 노드에 새로운 노드 지정
current = node1 #첫번째 노드를 현재 노드로 설정
print(current.data, end = ' ') #첫번째 노드의 데이터 출력
while current.link != None : #현재 링크가 비어있지 않는 동안 반복
current = current.link #반복 된다면 current.link.link ... 이런식으로 진행
print(current.data, end = ' ') #현재 노드의 데이터 출력다현 정연 지원 쯔위 사나 지효
#노드 삭제
class Node() :
def __init__ (self) :
self.data = None
self.link = None
node1 = Node() #첫번째 노드 생성
node1.data = '다현' #데이터에 다현 입력
node2 = Node() #두번째 노드 생성
node2.data = '정연' #데이터에 정연 입력
node1.link = node2 #첫번째 노드의 링크에 두번째 노드 연결
node3 = Node()
node3.data = '쯔위'
node2.link = node3
node4 = Node()
node4.data = '사나'
node3.link = node4
node5 = Node()
node5.data = '지효'
node4.link = node5
node2.link = node3.link #두번째 노드의 링크를 세번째 노드의 링크로 복사
del(node3) #세번째 노드 삭제
current = node1 #첫번째 노드를 현재 노드로 설정
print(current.data, end = ' ') #첫번째 노드의 데이터 출력
while current.link != None : #현재 링크가 비어있지 않는 동안 반복
current = current.link #반복 된다면 current.link.link ... 이런식으로 진행
print(current.data, end = ' ') #현재 노드의 데이터 출력다현 정연 사나 지효
#단순 연결 리스트 생성
##클래스와 함수 선언 부분##
class Node() : #기본 단위인 노드 생성
def __init__ (self) :
self.data = None #노드가 저장하는 데이터
self.link = None #다음 노드를 가리키는 포인터
def printNodes(start) : #연결 리스트의 노드들을 출력하는 함수
current = start #현재 노드를 시작 노드로 설정
if current == None : #리스트가 비어있는 경우 함수 종료
return
print(current.data, end = ' ') #현재 노드의 데이터 출력
while current.link != None : #다음 노드가 존재하는 동안 반복
current = current.link #현재 노드를 다음 노드로 이동
print(current.data, end = ' ') #련재 노드의 데이터 츨력
print()
## 전역 변수 선언 부분 ##
memory = []
head, current, pre = None, None, None
dataArray = ['다현', '정연', '쯔위', '사나', '지효']
## 메인 코드 부분 ##
if __name__ == "__main__" :
node = Node() #새로운 노드 생성
node.data = dataArray[0] #첫번째 데이터('다현')를 노드에 저장
head = node #첫번째 노드를 리스트의 시작 노드로 설정
memory.append(node) #생성된 노드를 memory 리스트에 추가
for data in dataArray[1:] : #데이터 배열의 두 번째 요소부터 마지막 요소까지 반복
pre = node #이전 노드를 현재 노드로 설정
node = Node() #새로운 노드를 생성
node.data = data #현재 데이터를 노드에 저장
pre.link = node #이전 노드의 링크를 새로운 노드로 설정
memory.append(node) #생성된 노드를 memory 리스트에 추가
printNodes(head) #연결 리스트의 모든 노드를 출력다현 정연 쯔위 사나 지효
#첫번째 노드 삽입# 8.22
node = Node() #새로운 노드 생성
node.data = '화사'
node.link = head #새로운 노드가 가리키는 것은 head가 가리키는 것과 같다
head = node #head노드를 새로운 노드로 지정
#중간에 삽입
current = head
while current.link != None :
pre = current #현재 노드를 이전 노드로 지정
current = current.link #현재 노드를 다음 노드로 이동
if current.data == '사나' : #현재 노드가 사나 일때
node = Node() #새로운 노드('솔라') 생성
node.data = '솔라'
node.link = current #새노드의 링크를 현재 노드로 지정
pre.link = node #이전 노드의 링크를 현재 노드에 지정
#마지막 노드 삽입#8.23
current = head
while current.link != None :
pre = current #현재 노드를 이전 노드로 지정
current = current.link #현재 노드를 다음 노드로 이동
if current.data != '재남' : #마지막 노드까지 재남이 없을 경우
node = Node() #새로운 노드('문별') 생성
node.data = '문별'
pre.link = node #이전 노드의 링크를 현재 노드에 지정
#단순 연결 리스트 노드 삽입 함수#
class Node() :
def __init__ (self) :
self.data = None
self.link = None
def printNodes(start) : #연결 리스트의 노드들을 출력하는 함수
current = start #현재 노드를 시작 노드로 설정
if current == None : #리스트가 비어있는 경우 함수 종료
return
print(current.data, end = ' ') #현재 노드의 데이터 출력
while current.link != None : #다음 노드가 존재하는 동안 반복
current = current.link #현재 노드를 다음 노드로 이동
print(current.data, end = ' ') #현재 노드의 데이터 츨력
print()
def insertNode(findData, insertData) :
global memory, head, current, pre
if head.data == findData :
node = Node()
node.data = insertData
node.link = head
head = node
return
current = head
while current.link != None :
pre = current #현재 노드를 이전 노드로 지정
current = current.link #현재 노드를 다음 노드로 이동
if current.data == findData : #현재 노드가 findData 일때
node = Node() #새로운 노드('insertData') 생성
node.data = insertData
node.link = current #새노드의 링크를 현재 노드로 지정
pre.link = node #이전 노드의 링크를 현재 노드에 지정
node = Node() #새로운 노드('insertData') 생성
node.data = insertData
pre.link = node #이전 노드의 링크를 현재 노드에 지정
##전역 변수 선언 부분
memory = []
head, current, pre = None, None, None
dataArray = ['다현', '정연', '쯔위', '사나', '지효']
## 메인 코드 부분 ##
if __name__ == "__main__" :
node = Node() #새로운 노드 생성
node.data = dataArray[0] #첫번째 데이터('다현')를 노드에 저장
head = node #첫번째 노드를 리스트의 시작 노드로 설정
memory.append(node) #생성된 노드를 memory 리스트에 추가
for data in dataArray[1:] : #데이터 배열의 두 번째 요소부터 마지막 요소까지 반복
pre = node #이전 노드를 현재 노드로 설정
node = Node() #새로운 노드를 생성
node.data = data #현재 데이터를 노드에 저장
pre.link = node #이전 노드의 링크를 새로운 노드로 설정
memory.append(node) #생성된 노드를 memory 리스트에 추가
printNodes(head) #연결 리스트의 모든 노드를 출력
insertNode('다현', '화사')
printNodes(head)
insertNode('사나', '솔라')
printNodes(head)
insertNode('재남', '문별')
printNodes(head)다현 정연 쯔위 사나 지효
화사 다현 정연 쯔위 사나 지효
화사 다현 정연 쯔위 솔라 사나 솔라
화사 다현 정연 쯔위 솔라 사나 문별
#첫번째 노드 삭제 과정
current = head #현재 노드를 삭제할 노드인 head와 동일하게 만들기
head = head.link #head를 삭제할 노드가 가르키던 다음노드로 변경된다
del(current)
#['다현', '정연', '쯔위', '사나', '지효']에서 쯔위 노드 삭제 과정
current = head
while 마지막 노드까지 :
pre = current #현재 노드를 이전 노드로 저장하고, 현재 노드를 다음 노드로 이동
current = current.link
if current.data == '쯔위' : #현재 노드가 '쯔위'라면 이전 노드의 링크를 현재 노드의 링크로 저장
pre.link = current.link
del(current) #현재 노드 삭제
#단순 연결 리스트의 노드 삭제 함수
#함수 선언 부분#
class Node() :
def __init__ (self) :
self.data = None
self.link = None
def printNodes(start) : #연결 리스트의 노드들을 출력하는 함수
current = start #현재 노드를 시작 노드로 설정
if current == None : #리스트가 비어있는 경우 함수 종료
return
print(current.data, end = ' ') #현재 노드의 데이터 출력
while current.link != None : #다음 노드가 존재하는 동안 반복
current = current.link #현재 노드를 다음 노드로 이동
print(current.data, end = ' ') #련재 노드의 데이터 츨력
print()
def deleteNode(deleteData) :
global memory, head, current, pre
if head.data == deleteData : #첫번쩨 노드 삭제
current = head
head = head.link
del(current)
return
current = head #첫번째 노드 외 삭제
while current.link != None :
pre = current
current = current.link
if current.data == deleteData :
pre.link = current.link
del(current)
return
#전역 변수 선언 부분#
memory = []
head, current, pre = None, None, None
dataArray = ['다현', '정연', '쯔위', '사나', '지효']
#메인 코드 부분#
if __name__ == "__main__" :
node = Node() #새로운 노드 생성
node.data = dataArray[0] #첫번째 데이터('다현')를 노드에 저장
head = node #첫번째 노드를 리스트의 시작 노드로 설정
memory.append(node) #생성된 노드를 memory 리스트에 추가
for data in dataArray[1:] : #데이터 배열의 두 번째 요소부터 마지막 요소까지 반복
pre = node #이전 노드를 현재 노드로 설정
node = Node() #새로운 노드를 생성
node.data = data #현재 데이터를 노드에 저장
pre.link = node #이전 노드의 링크를 새로운 노드로 설정
memory.append(node) #생성된 노드를 memory 리스트에 추가
printNodes(head) #연결 리스트의 모든 노드를 출력
deleteNode('다현')
printNodes(head)
deleteNode('쯔위')
printNodes(head)
deleteNode('지효')
printNodes(head)
deleteNode('재남')
printNodes(head)다현 정연 쯔위 사나 지효
정연 쯔위 사나 지효
정연 사나 지효
정연 사나
정연 사나
#노드 검색
current = head
if current == findData :
return current
while current.link != None :
current = current.link
if current == findData :
return current
return Node()
def findNode(findData) :
global memory, head, current, pre
current = head
if current.data == findData :
return current
while current.link != None :
current = current.link
if current.data == findData :
return current
return Node()
#단순 연결 리스트의 노드 검색 함수
class Node() :
def __init__ (self) :
self.data = None
self.link = None
def printNodes(start) : #연결 리스트의 노드들을 출력하는 함수
current = start #현재 노드를 시작 노드로 설정
if current == None : #리스트가 비어있는 경우 함수 종료
return
print(current.data, end = ' ') #현재 노드의 데이터 출력
while current.link != None : #다음 노드가 존재하는 동안 반복
current = current.link #현재 노드를 다음 노드로 이동
print(current.data, end = ' ') #현재 노드의 데이터 츨력
print()
def findNode(findData) :
global memory, head, current, pre
current = head
if current.data == findData :
return current
while current.link != None :
current = current.link
if current.data == findData :
return current
return Node()
#전역 변수 선언 부분#
memory = []
head, current, pre = None, None, None
dataArray = ['다현', '정연', '쯔위', '사나', '지효']
#메인 코드 부분#
if __name__ == "__main__" :
node = Node() #새로운 노드 생성
node.data = dataArray[0] #첫번째 데이터('다현')를 노드에 저장
head = node #첫번째 노드를 리스트의 시작 노드로 설정
memory.append(node) #생성된 노드를 memory 리스트에 추가
for data in dataArray[1:] : #데이터 배열의 두 번째 요소부터 마지막 요소까지 반복
pre = node #이전 노드를 현재 노드로 설정
node = Node() #새로운 노드를 생성
node.data = data #현재 데이터를 노드에 저장
pre.link = node #이전 노드의 링크를 새로운 노드로 설정
memory.append(node) #생성된 노드를 memory 리스트에 추가
printNodes(head) #연결 리스트의 모든 노드를 출력
fNode = findNode('다현')
print(fNode.data)
fNode = findNode('쯔위')
print(fNode.data)
fNode = findNode('재남')
print(fNode.data)다현 정연 쯔위 사나 지효
다현
쯔위
None
#사용자가 입력한 정보 관리하기#
#클래스와 함수 선언 부분#
class Node() :
def __init__ (self) :
self.data = None
self.link = None
def printNodes(start) :
current = start
if current == None :
return
print(current.data, end = ' ')
while current.link != None :
current = current.link
print(current.data, end = ' ')
print()
def makeSimpleLinkedList(nameEmail) :
global memory, head, current, pre
node = Node()
node.data = nameEmail
memory.append(node)
if head == None :
head = node
return
if head.data[1] > nameEmail[1] :
node.link = head
head = node
return
current = head
while current.link != None :
pre = current
current = current.link
if current.data[1] > nameEmail[1] :
pre.link = node
node.link = current
return
current.link = node
#전역 변수 선언 부분#
memory = []
head, current, pre = None, None, None
#메인 코드 부분#
if __name__ == '__main__' :
while True :
name = input('이름 -->')
if name == '' or name == None :
break
email = input('이메일 -->')
makeSimpleLinkedList([name, email])
printNodes(head)이름 --> 헤리
이메일 --> herry@girls.com
['헤리', 'herry@girls.com']
이름 --> 유라
이메일 --> youra@girls.com
['헤리', 'herry@girls.com'] ['유라', 'youra@girls.com']