학습 목표
- 단순 연결 리스트의 개념 파악
- 단순 연결 리스트와 선형 리스트의 차이 이해
- 단순 연결 리스트의 데이터 삽입/삭제 원리 이해
- 파이썬으로 단순 연결 리스트 조작하는 코드 작성
Section00. 생활 속 자료구조와 알고리즘
지도에 방문할 식당 연결한 것-->연결 리스트의 형태
Section01. 단순 연결 리스트의 기본(Singly Linked List)
1. 단순 연결 리스트의 개념
단순 연결 리스트에서는 저장된 노드들이 물리적으로 떨어진 곳에 위치
선형 리스트에서는 삽입하거나 삭제할 때 칸을 이동해야하는 번거로움이 있어서 데이터 크기가 커질수록 비효율적
=>오버헤드: 과하게 발생하는 작업
단순 연결 리스트에서 데이터 삽입: 오버헤드 없음
새로운 데이터가 담긴 노드를 임의 위치에 준비한 후 해당 노드의 앞뒤 링크만 수정하면 기존 노드는 변경 없이 그대로 유지됨
2. 단순 연결 리스트의 원리
🤎노드 구조
-선형 리스트는 배열에 순서대로 저장되기 때문에 데이터만 있으면 됨
-단순 연결 리스트는 다음 데이터를 가리키는 링크(Link)가 더 필요(화살표 개념)
-노드(Node): 데이터와 링크로 구성된 항목
링크에 다음 노드를 가리키는 주소가 들어감
마지막 노드의 링크에는 빈 값을 넣어 마지막 노드임을 표시
단순 연결 리스트에서는 첫 번째 노드를 가리키는 헤드(head)를 사용
단순 연결 리스트가 한쪽 방향으로만 진행되어 다음 노드로는 찾아갈 수 있지만 이전 노드로는 돌아갈 수 없는데, 헤드를 이용하면 처음부터 다시 진행 가능
(헤드에서 재시작 가능)
🤎노드(데이터) 삽입
삽입할 노드 생성해서 순서에 맞게 링크 수정
1단계: 새 노드 생성
2단계: 링크 수정
🤎노드(데이터)삭제
1단계: 링크 수정
2단계: 노드 삭제
Section02. 단순 연결 리스트의 간단 구현
1. 노드 생성과 연결
단순 연결 리스트를 구현하려면 먼저 노드를 구현해야 함
클래스 이용
🤎노드 생성
Node 데이터형 정의
class Node():
def __init__ (self):
self.data = None
self.link = Noneex) '다현(트와이스)' 노드 만들기
1행에서 빈 노드 생성
2행에서 다현을 data에 대입
node1 = Node()
node1.data="다현"🤎노드 연결
ex)두 번재 정연 노드를 생성하고, 정연 노드를 첫 번째 노드의 링크로 연결
node2 = Node()
node2.data = "정연"
node1.link=node #첫 번째 노드의 링크에 두 번째 노드를 넣어 연결
2. 데이터가 5개인 단순 연결 리스트 생성
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이런 식으로 첫 번째 노드를 기준으로 마지막 노드까지 전체를 접근하고 출력할 수 있다
다현의 다음 node1.link
다현의 다음 데이터 node1.link.data
다현의 다음다음 데이터 node1.link.link.data
다현의 다음다음다음 데이터 node1.link.link.link.data
노드의 처음부터 끝까지 출력하기
①첫 번재 노드를 현재(current) 노드로 지정하고, 현재 노드의 데이터인 다현을 출력
②현재 노드의 링크가 비어 있지 않다면 현재 노드를 현재 노드의 링크가 가리키는 노드로 변경한 후 현재 노드의 데이터인 정연 출력
③앞의 2단계를 반복하다 현재 노드의 링크가 비어있으면 종료
데이터가 5개인 단순 ㅇ녀결 리스트 생성
current=node1
print(current.data, end=' ')
while current.link != None:
current=current.link
print(current.data, end=' ')
3. 노드 삽입
새 노드 생성하고 데이터 입력
앞의 노드 링크 복사
앞의 노드 링크에 새로 만든애 링크로 연결
newNode=Node()
newNode.data="재남"
newNode.link=node2.link
node2.link=newNode
4. 노드 삭제
삭제할 노드의 링크를 바로 앞 노드의 링크로 복사
그러면 뒷노드가 그 앞의 노드랑 링크로 연결
연결 다 끊으면 삭제하기
node2.link=node3.link
del(node3)
Section03. 단순 연결 리스트의 일반 구현
1. 단순 연결 리스트의 일반 형태
생성되는 모든 노드를 메모리 공간에 넣어 둘 것
실제로 노드의 순서는 상관없이 링크로만 연결됨
-헤드(head): 첫 번째 노드
-현재(current): 지금 처리 중인 노드
-이전(pre): 현재 처리 중인 노드의 바로 앞 노드
처음에는 모두 비어 있으면 되므로 초기화 하기!
memory=[]
head, current, pre = None, None, None
2. 배열에 저장된 데이터 입력 과정
사용자가 입력하거나 배열에서 데이터를 추출한 후 값을 계속 단순 연결 리스트로 만드는 코드 작성하기
작동 순서는 첫 번째 데이터와 두 번재 이후 데이터로 나누어 생각해 볼 수 있음
🤎데이터 입력 과정
먼저 첫 번재 데이터는 빈 노드를 생성하고 키도드로 데이터를 입력하거나 데이터 저장소에서 데이터를 가져와서 대입
완성된 노드를 메모리에 넣음
모든 노드는 head를 시작으로 연결됨, 사용자가 원하는 만큼 데이터 입력 가능
node=Node()
node.data=dataArray[0]
head=node
memory.append(node)두 번재 이후 데이터는 새 노드를 기존 노드의 링크에 저장하기 전에 기존 노드를 잠시 저장한 후 생성하기
①기존 노드를 임시 저장
②빈 노드 생성
③데이터 입력(직접 입력 또는 가져오기)
④이전(pre)의 링크를 새 노드에 대입
⑤새 노드를 메모리에 넣음
pre=node
node=Node()
node.data=data
preNode.link=node
memory.append(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()
#전역변수 선언 부분
memory=[]
head, current, pre=None, None, None
dataArray=["다현", "정연", "쯔위", "사나", "지효"]
#메인 코드 ㅜ분
if __name__=="__main__":
node=Node() #첫번째노드
node.data=dataArray[0]
head=node
memory.append(node)
for data in dataArray[1:] : #두번째이후노드
pre=node
node=Node()
node.data=data
pre.link=node
memory.append(node)
printNodes(head)
3. 노드 삽입
🤎첫 번째 노드 삽입
노드 생성, 새 노드의 링크로 헤드 노드가 가리키는 노드 지정, 헤드 노드를 새 노드로 지정
node=Node()
node.data="화사"
node.link=head
head=node🤎중간 노드 삽입
ex) 사나 노드 앞에 솔라 노드 삽입하는 과정
헤드에서 시작해서 현재노드가 사나인지 확인
현재 노드를 이전pre)노드로 저장하고, 현재 노드를 다음 노드로 이동한다. 그리고 현재 노드가 사나인지 확인
현재 노드가 사나일 때까지 2단계 반복
현재 노드가 사나라면 우선 새 노드(솔라 노드)를 생성한 후 이전 노드의 리으를 새 노드의 링크로 지정한다.
이전 노드의 링크를 새 노드로 지정한다.
current=head
while 마지막 노드까지:
pre = current
current=current.link
if current.data=="사나":
node=Node()
node.data="솔라"
node.link=current
pre.link=node🤎마지막 노드 삽입
1~3 중간 노드 삽입 과정과 동일하므로 없는 데이터인 재남을 찾는다.
마지막 노드까지 재남을 찾지 못했다면 우선 새노드를 생성한 후 현재 노드의 링크를 새 노드로 지정한다.
(1~3 단계를 실행했으므로 현재 노드는 마지막 노드가 된다)
#마지막 노드까지 "재남"을 찾지 못한 후
node=Node()
node.data="문별"
current.link=node🤎노드 삽입 함수의 완성
세 가지 경우의 데이터를 입력하는 함수 작성
함수의 매개변수로 찾을 데이터와 삽입할 데이터를 받도록 함
class Node():
#위의 코드와 동일
def printNodes(start):
#위의 코드와 동일
#첫 번재 노드 삽입
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:
node=Node()
node.data=insertdata
node.link=current
pre.link=node
return
#마지막 노드 상입
node=Node()
node.data=insertData
current.link=node
#전역변수선언부분
#동일
#메인코드 부분
if __name__=="__main__":
#동일생략
4. 노드 삭제
🤎첫 번재 노드 삭제
현재 노드를 삭제할 노드인 헤드와 동일하게 만듦
헤드를 삭제할 노드의 링크가 가리키던 노드로 변경
현재 노드를 메모리에서 제거
current=head
head=head.link
del(current)🤎첫 번재 외 노드 삭제
헤드에서 시작해서 현재노드가 삭제할 대상인지 확인
현재 노드를 이전 노드(pre)로 저장하고, 현재 노드를 다음 노드로 이동
긜고 현재 노드가 삭제할 애인지 확인
현재 노드가 삭제할 애일 때까지 계속 반복
현재 노드가 삭제할 애라면 이전 녿의 링크를 현재 노드의 링크(=삭제할 애 다음애)로 지정
현재 노드를 메모리에서 삭제
current=head
while 마지막 노드까지:
pre=current
current=current.link
if current.data=="쯔위":
pre.link=current.link
del(current)🤎노드 삭제 함수의 완성
classNode():
#생략
def printNodes(start):
#생략
def deleteNode(deleteData):
global memory, ehad, 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
#전역변수선언부분
#생략
#메인코드 부분
if __name__=="__main__":
#생략
5. 노드 검색
검색할 데이터의 노드 반호나하는 방식으로 처리하기
①현재 노드(current)를 첫 번째 노드인 헤드(head)와 동일하게 만들고, 현재 노드가 검색할 데이터인지 비교
검색할 데이터와 동일하다면 현재 노드 반환
②현재 노드를 다음 노드로 이동, 검색할 데이터와 동일하다면 현재 노드를 반환
③앞의 2단계를 끝까지 진행하고, 검색할 데이터를 찾지 못했다면 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(curretn.data, end=' ')
print()
def findNode(findData):
global memory, head, current, pre
current=head
if current.data==findData:
reutrn 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)
for data in dataArray[1:]: #두 번째 이후 노드
pre=node
node=Node()
node.data=data
pre.link=node
memory.append(node)
printNodes(head)
fNode=findNode("다현")
print(fNode.data)
Section04. 단순 연결 리스트의 응용
간단한 [명함관리] 프로그램
이름과 연락처를 무작위로 입력하면 이름 순서대로 단순 연결 리스트에 저장하는 기능
①입력할 데이터를 2차원 배열에 저장
dataArray=[["지민", "010-1111-1111"], ["정국", "010-2222-2222"], ["뷔", "010-3333-3333"], ["슈가", "010-4444-4444"], ["진", "010-5555-5555"]]②데이터를 차례대로 가져옴
헤드가 비어있을 때는 헤드에 첫 노드를 지정
head=node③두 번째 정국을 대입
새로운 데이터가 첫 노드보다 작다면 새 노드의 링크에 첫 노드를 입력하고, 헤드에는 새 노드를 지정
node.link=head
head=node④다음으로 뷔 대입
역시 새로운 데이터가 첫 노드보다 작다면 새 노드의 링크에 첫 노드를 입력하고, 헤드에는 새 노드를 지정한다.
⑤다음으로 슈가 입력
슈가는 첫 노드보다 크기 때문에 중간에 삽입됨
현재 노드와 이전 노드를 이용해서 현재 노드가 슈가보다 크면 이전 노드 링크를 슈가로 지정하고, 슈가 노드의 링크를 현재 노드로 지정한다.
current=head
while 노드의 끝까지:
pre=current
current=current.link
if 현재노드>입력할노드:
pre.link=node
node.link=current⑥마지막으로 진을 입력
진은 마지막 노드보다 크므로 마지막에 추가
current.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 makeSimpleLinkedList(namePhone):
global memory, head, current, pre
printNodes(head)
node=Node()
node.data=namePhone
memory.append(node)
if head==None: #첫번째 노드일 때
head=node
return
if node.data[0]>namePhone[0]: #첫 번째 노드보다 작을 때
node.link=head
head=node
return
#중간 노드로 삽입하는 경우
current=head
while current.link!=None:
pre=current
current=current.link
if current.data[0]>namePhone[0]:
pre.link=node
node.link=current
return
#삽입하는 노드가 가장 큰 경우
current.link=node
#전역 변수 선언 부분
memory=[]
head, current, pre=None, None, None
dataArray=[["지민", "010-1111-1111"], ["정국", "010-2222-2222"], ["뷔", "010-3333-3333"], ["슈가", "010-4444-4444"], ["진", "010-5555-5555"]]
#메인 코드 부분
if __name__=="__main__":
for data in dataArray:
makeSimpleLinkedList(data)
printNodes(head)
<연습문제>
1. 정답) 선형리스트, 단순 연결리스트
선형리스트에서는 배열에 데이터를 차례대로 저장하므로 데이터의 실제 위치 순서로 데이터가 구성된다.
단순 연결리스트에서는 데이터를 노드 단위로 삽입/삭제한다.
2. 정답)3
선형 리스트와 비교한 단순 연결 리스트에 대한 설명. 거리가 먼 것 찾기
①물리적으로 연결되어 있지 않은 데이터가 연결된다.
②연결을 위한 링크가 필요하다.
③중간에 새로운 데이터를 삽입할 때는 비효율적이다.
④노드(Node)를 사용해서 데이터를 표현한다.
3. 노드 구조에서 a와 b를 무엇이라고 하나요?
정답) a: 데이터 b: 링크
4. 그림과 같이 노드를 생성하고 연결하는 코드를 차례대로 올바르게 나열한 것은?
정답)2
node1=Node()
node1.data="다현"
node2=Node()
node2.data="정연"
node1.link=node2
5. 단순 연결 리스트의 맨 앞 데이터를 삭제하는 ㅗ드
current=head
head=head.link
del(current)
6. 쯔위 출력 코드
정답)4
print(node1.link.link.data)
7.
정답) node.data
node.link
data
8.
정답) 2
while current.link!=None
이 책의 저자는 아이돌을 무척이나 좋아한다... 특히 트와이스
'프로그래밍 > 자료구조' 카테고리의 다른 글
| [파이썬 자료구조와 알고리즘] Chapter 07. 큐 (0) | 2022.08.14 |
|---|---|
| [파이썬 자료구조와 알고리즘] Chapter 05. 원형 연결 리스트 (0) | 2022.08.05 |
| [파이썬 자료구조와 알고리즘] Chapter 03. 선형 리스트 (0) | 2022.08.04 |
| [파이썬 자료구조와 알고리즘] Chapter 02. 파이썬 기초 문법과 데이터 형식 (0) | 2022.08.03 |
| [파이썬 자료구조와 알고리즘] Chapter 01. 자료구조와 알고리즘 소개 (0) | 2022.08.03 |