728x90
728x90
단순 연결 리스트(Singly Linked List)
단순 연결 리스트의 개념
선형 리스트(Linear List)
- 장점
- 배열에 구성하였기 때문에 단순하다.
- 물리적인 순서와 논리적인 순서가 동일하여 데이터를 찾기 간단하다.
- 프로그램으로 구현하기 비교적 쉽다.
- 단점 : 데이터를 삽입하거나 삭제할 때 많은 작업이 필요하다.
- 예) 100만 개인 선형 리스트의 맨 앞에 데이터를 하나 삽입하려면 약 100만 개를 뒤로 이동시키는 작업을 해야 한다. (오버헤드(Overhead) 발생)
단순 연결 리스트(Singly Linked List)
- 선형 리스트(Linear List)와 달리, 저장된 노드들이 물리적으로 떨어진 곳에 위치한다.
- 각 노드의 번지도 100, 200, 130 등으로 순차적이지 않다.
- 데이터와 링크로 구성된 항목인 노드(Node)로 이루어진다.
- 단순 연결 리스트에는 첫 번째 노드를 가리키는 헤드(head)를 사용한다.
- 단순 연결 리스트가 한쪽 방향으로만 진행되어 다음 노드로 찾아갈 수 있지만, 이전 노드로는 돌아갈 수 없는데 헤드를 이용하면 처음부터 다시 진행이 가능하다.
노드(데이터) 삽입
- 1단계 : 삽입할 노드를 생성한다.
- 2단계 : 순서에 맞게 링크를 수정한다.
- 새 노드의 링크에 이전 노드의 링크를 복사한다.
- 이전 노드의 링크에 새 노드를 지정한다.
노드(데이터) 삭제
- 1단계 : 삭제할 노드의 바로 앞 노드 링크를 수정한다.
- 삭제할 노드의 링크를 바로 앞 노드의 링크로 복사하여 앞 노드가 삭제할 노드의 다음 노드를 가리키게 한다.
- 2단계 : 삭제할 노드를 삭제한다.
단순 연결 리스트의 구현
- 헤드(head) : 첫 번째 노드를 가리킨다.
- 현재(current) : 지금 처리 중인 노드를 가리킨다.
- 이전(pre) : 현재 처리 중인 노드의 바로 앞 노드를 가리킨다.
- 처음에는 모두 비어 있으므면 되므로 다음과 같이 초기화한다.
memory = []
head, current, pre = None, None, None
① 단순 연결 리스트 생성
노드 생성
- 노드는 클래스(Class)를 사용하여 구현한다.
class Node() :
def __init__(self): # 생성자 함수 : 데이터형을 생성할 때 자동으로 실행
self.data = None
self.Link = None
- 노드 생성 및 확인
node1 = Node()
node1.data = "Apple"
print(node1.data, end = ' ')
노드 연결
- 첫 번째 노드의 링크에 두 번째 노드 이름(node2)을 넣어 주면 두 노드가 단순 연결 리스트로 연결된다.
node2 = Node()
node2.data = "Banana"
node1.link = node2 # 첫 번째 노드의 링크에 두 번째 노드를 넣어 연결
노드 초기화
첫 번째 데이터
- 모든 노드는 head를 시작으로 연결된다.
- 그리고 사용자가 원하는 만큼 데이터를 입력할 수 있다.
node = Node()
node.data = dataArray[0] # 첫 번째 노드
head = node
memory.append(node)
두 번째 이후 데이터
- 새 노드를 기준 노드의 링크에 저장하기 전에 기존 노드를 잠시 저장한 후 생성해야 한다.
pre = node
node = Node()
node.data = data # 두 번째 이후 노드
pre.link = node
memory.append(node)
② 노드 삽입
- 노드를 단순 연결 리스트의 맨 앞, 중간, 마지막에 삽입하는 경우로 나누어 생각해 볼 수 있다.
첫 번째 노드 삽입
node = Node()
node.data = item
node.link = head
head = node
중간 노드 삽입
current = head
while 마지막 노드까지 :
pre = current
current = current.link
if current.data == origin_data :
node = Node()
node.data = new_data
node.link = current
pre.link = node
마지막 노드 삽입
# 마지막 노드까지 new_data 를 찾지 못한 후
node = Node()
node.data = new_data
current.link = node
함수 완성
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
③ 노드 삭제
첫 번째 노드 삭제
current = head
head = head.link
del(current)
첫 번째 외 노드 삭제
current = head
while 마지막 노드까지 :
pre = current
current = current.link
if current.data == finding_data :
pre.link = current.link
del(current)
함수 완성
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
④ 노드 검색
- 검색할 데이터의 노드를 반환하는 방식으로 구현해본다.
함수 완성
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 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
# 노드 삭제 함수
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
# 노드 검색 함수
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)
# 두 번째 이후 노드
for data in dataArray[1:]:
pre = node
node = Node()
node.data = data
pre.link = node
memory.append(node)
printNodes(head)
# 삽입 예
insertNode("다현", "화사")
printNodes(head)
insertNode("사나", "솔라")
printNodes(head)
insertNode("지민", "문별") # 존재하지 않는 데이터인 지민 노드 앞에 문별 노드를 삽입한 후 출력 (맨 마지막에 삽입)
printNodes(head)
# 삭제 예
deleteNode("다현")
printNodes(head)
deleteNode("쯔위")
printNodes(head)
deleteNode("지효")
printNodes(head)
deleteNode("지민")
printNodes(head)
# 검색 예
fNode = findNode("다현")
print(fNode.data)
fNode = findNode("쯔위")
print(fNode.data)
fNode = findNode("지민")
print(fNode.data)
더보기
더보기
다현 정연 쯔위 사나 지효
화사 다현 정연 쯔위 사나 지효
화사 다현 정연 쯔위 솔라 사나 지효
화사 다현 정연 쯔위 솔라 사나 지효 문별
화사 정연 쯔위 솔라 사나 지효 문별
화사 정연 솔라 사나 지효 문별
화사 정연 솔라 사나 문별
화사 정연 솔라 사나 문별
None
None
None
(참고) 이중 연결 리스트(Doubly Linked List)
개념
- 양방향으로 링크가 연결되어 노드의 양방향으로 접근하기가 용이한 리스트
구현
노드
- 2개의 링크와 1개의 데이터가 한 노드로 구성된다.
- 앞의 노드를 가리크는 링크 : plink
- 다음 노드를 가리키는 링크 : nlink
class Node2() :
def __init__ (self) :
self.plink = None # 앞쪽 링크
self.data = None
self.nlink = None # 뒤쪽 링크
코드
- 단순 연결 리스트를 구현했던 코드에서 노드를 약간 수정하여 이중 연결 리스트처럼 출력해본다.
## 클래스와 함수 선언 부분 ##
class Node2() :
def __init__ (self) :
self.plink = None # 앞쪽 링크
self.data = None
self.nlink = None # 뒤쪽 링크
def printNodes(start):
current = start
if current.nlink == None :
return
print("정방향 --> ", end=' ')
print(current.data, end=' ')
while current.nlink != None:
current = current.nlink
print(current.data, end=' ')
print()
print("역방향 --> ", end=' ')
print(current.data, end=' ')
while current.plink != None:
current = current.plink
print(current.data, end=' ')
## 전역 변수 선언 부분 ##
memory = []
head, current, pre = None, None, None
dataArray = ["다현", "정연", "쯔위", "사나", "지효"]
## 메인 코드 부분 ##
if __name__ == "__main__" :
node = Node2() # 첫 번째 노드
node.data = dataArray[0]
head = node
memory.append(node)
for data in dataArray[1:] : # 두 번째 이후 노드
pre = node
node = Node2()
node.data = data
pre.nlink = node
node.plink = pre
memory.append(node)
printNodes(head)
더보기
정방향 --> 다현 정연 쯔위 사나 지효
역방향 --> 지효 사나 쯔위 정연 다현
728x90
728x90
'Computer Science > 자료구조' 카테고리의 다른 글
[C] 원형 연결 리스트(Circular Linked List) (0) | 2022.07.12 |
---|---|
[C] 단순 연결 리스트(Singly Linked List) (0) | 2022.07.12 |
[Python] 큐(Queue) (0) | 2022.07.01 |
[Python] 스택(Stack) (0) | 2022.07.01 |
[Python] 이진 탐색(Binary Search) (0) | 2022.06.29 |
[Python] 순차 탐색(Sequential Search) (0) | 2022.06.29 |
[Python] 원형 연결 리스트(Circular Linked List) (0) | 2022.06.22 |
[Python] 선형 연결 리스트(Linear Linked List) (0) | 2022.06.22 |