03-1 리스트란?
리스트(list) 또는 선형 리스트(linear list)는 자료들이 차례대로 나열된 선형 자료구조
각 자료는 순서 또는 위치(position)를 가짐
리스트에서는 어떤 위치에서도 새로운 요소를 삽입할 수 있음
어느 위치에 요소를 삽입 → 이후 모든 자료가 한 칸씩 뒤로 밀림
어느 위치의 요소를 삭제 → 이후 모든 자료가 한 칸씩 당겨짐
리스트 - 집합(Set)
리스트: 순서 O, 중복 허용
집합: 원소 사이에 순서 X, 중복 허용 X
집합은 원소 사이에 순서의 개념이 없으므로 선형 자료구조라 볼 수 없음
리스트의 연산
- insert(pos, e) : pos 위치에 새로운 요소 e를 삽입
- delete(pos) : pos 위치에 있는 요소를 꺼내서 반환
- getEntry(pos) : pos 위치에 있는 요소를 삭제하지 않고 반환
- isEmpty() : 리스트가 비어 있으면 True를, 아니면 False를 반환
- isFull() : 리스트가 가득 차 있으면 True를, 아니면 False를 반환
- size() : 리스트에 들어 있는 전체 요소의 수를 반환
03-2 배열 구조와 연결된 구조
배열 구조
모든 요소는 중간에 빈자리가 없이 반드시 메모리의 연속된 공간에 저장됨
연결된 구조(linked structure)
요소들이 메모리의 여기저기에 흩어져서 저장됨
메모리에 흩어져 있는 요소들을 링크(link)를 이용하여 순서대로 연결해 관리
연결 리스트(linked list)
자료들을 링크를 통해 일렬로 나열할 수 있는 연결된 구조
연결 리스트는 노드(node)로 구성되어 있고 노드는 데이터와 함께 링크를 가짐
배열 구조의 리스트와 연결 리스트의 비교
리스트 요소들에 대한 접근
리스트의 k번재 요소에 접근
• 배열 구조
모든 요소의 크기가 같고 연속된 메모리 공간에 있다는 전제 조건
한 요소의 크기에 원하는 위치(k)를 곱해 시작주소에 더해 주면 계산됨
→ 계산하는 데 걸리는 시간은 k와 상관없이 곱셈과 덧셈을 한 번씩 사용
• 연결된 구조
시작 노드의 주소만 알고 있어, k번째 요소를 찾으려면 시작 노드에서부터 k-1번 링크를 따라 이동해야 함
리스트의 용량
• 배열 구조
용량이 고정됨
→ 중간에 부족하다고 늘리거나 필요 없다고 줄이기 어려움
• 연결된 구조
용량이 고정되어 있지 X
필요할 때 필요한 크기만큼 새로 할당해서 사용
리스트의 삽입 연산
• 배열 구조
중간에 자료를 삽입하려면 그 위치 이후의 모든 요소를 한 칸씩 뒤로 밀어야 함
• 연결된 구조
삽입할 위치의 앞 노드 링크와 새로운 요소의 링크만 수정하면 됨
리스트의 삭제 연산
• 배열 구조
중간에 있는 자료를 삭제하면 이후의 모든 자료를 앞으로 당겨 빈 곳이 생기지 않도록 해야 함
• 연결된 구조
삭제할 노드 바로 앞 노드의 링크만 수정하면 됨
03-3 배열 구조의 리스트: 파이썬 리스트
파이썬 리스트는 자료 구조 리스트를 배열 구조로 구현한 하나의 사례
파이썬 리스트
| 멤버함수(메서드) | 설명 |
| append(e) | 새로운 요소 e를 추가합니다. |
| extend(lst) | 리스트 lst를 리스트 s에 삽입합니다. |
| count(e) | 리스트에서 요소 e의 개수를 세어 반환합니다. |
| index(e, [시작], [종료]) | 요소 e가 나타나는 가장 작은 위치(인덱스)를 반환합니다. 탐색을 위한 시작 위치와 종료 위치를 지정할 수도 있습니다. |
| insert(pos, e) | pos 위치에 새로운 요소 e를 삽입합니다. |
| pop(pos) | pos 위치의 요소를 꺼내고 반환합니다. |
| pop() | 맨 뒤의 요소를 꺼내고 반환합니다. |
| remove(e) | 요소 e를 리스트에서 제거합니다. |
| reverse() | 리스트 요소들의 순서를 뒤집습니다. |
| sort([key], [reverse]) | 요소들을 key를 기준으로 오름차순으로 정렬합니다. reverse=True이면 내림차순으로 정렬합니다. |
파이썬의 리스트는 배열 구조로 구현되어 있으므로 원소의 접근은 효율적이지만, 삽입과 삭제 연산은 효율적이지 않음
파이썬 리스트는 용량이 제한되지 않도록 구현되었습니다.
파이썬 리스트는 배열 구조를 사용하지만 용량이 제한되지 않도록 내부적으로 구현되어 있음
새로운 요소 삽입 시, 용량이 부족할 경우 파이썬 리스트가 내부적으로 용량을 늘리는 방법
- 1단계: 기존의 리스트보다 용량을 늘린 새로운 리스트를 할당
- 2단계: 기존의 리스트의 모든 요소를 새로운 리스트에 모두 복사
- 3단계: 새로운 리스트에 새로운 요소를 삽입
- 4단계: 기존 리스트 대신에 새로운 리스트를 사용
append() 연산은 용량이 포화되기 전이라면 매우 빨리 처리되지만 포화 상태라면 훨씬 많은 시간이 걸림
→ 파이썬 리스트의 append() 연산은 처리 시간이 항상 같지는 않음
03-4 연결 리스트의 구조와 종류
연결 리스트의 구조
노드(node)
연결 리스트에서 하나의 노드(node)는 하나의 데이터(data)와 함께 하나 이상의 링크(link)를 가짐
데이터(data): 리스트에 저장하고 싶은 자료
링크(link): 다른 노드를 가리키는(다른 노드의 주소를 저장하는) 변수
헤드 포인터(head pointer)
머리 노드(head node): 시작 노드
헤드 포인터(head pointer): 머리 노드의 주소를 저장하는 변수
꼬리 노드(tail node): 마지막 노드
꼬리 노드의 링크를 처리하는 방법에 따라 단순 연결과 원형 연결로 구분
연결 리스트의 종류
노드의 형태와 연결된 구조에 따라 연결 리스트를 나눌 수 있음
단순 연결 리스트(singly linked list)
하나의 방향으로만 연결된 리스트
노드는 하나의 링크를 갖고, 다음 노드의 주소가 저장됨
꼬리 노드의 링크는 마지막 노드라는 것을 나타내기 위해 None을 가짐
원형 연결 리스트(circular linked list)
꼬리 노드의 링크가 None이 아니라 다시 머리 노드를 가리키도록 함
→ 어떤 노드에서 시작해도 다른 모든 노드를 찾아갈 수 있음
노드들을 순서대로 방문할 때 종료 조건 처리에 조심해야 함
이중 연결 리스트(doubly linked list)
하나의 노드가 이전 노드(previous node)와 다음 노드의(next node) 링크를 모두 가리킴
어떤 노드에서 이전 노드를 바로 찾아갈 수 있는 장점이 있음
03-5 단순 연결 구조로 리스트 구현하기
단순 연결 구조의 노드 클래스를 구현해 봅시다.
Node 클래스의 정의와 생성자
노드는 데이터 필드와 하나의 링크를 가짐
link는 디폴트 인수 기능을 이요해 인수가 전달되지 않으면 None으로 자동으로 초기화되도록 함
단순 연결 구조를 위한 Node 클래스
class Node:
def __init__ (self, elem, link=None):
self.data = elem # 데이터 멤버 생성 및 초기화
self.link = link # 링크 생성 및 초기화
새로운 노드를 뒤에 추가하는 append() 연산
현재 노드 self 뒤에 새로운 노드 node 추가
- node의 링크가 self.link를 가리키게 함
- self의 링크가 node를 가리키게 함
Node 클래스: append(node) 연산
def append (self, node): # self 다음에 node를 넣는 연산
if node is not None:
node.link = self.link
self.link = node삽입할 노드가 None이 아니면 1, 2단계를 통해 node를 다음 노드로 연결
다음 노드를 연결 구조에서 꺼내는 Node 클래스의 popNext() 연산
현재 노드 self 뒤에 있는 노드 self.link(next)를 연결된 구조에서 꺼내고 반환
- 변수 next가 삭제할 노드 self.link를 가리키게 함
- self의 링크가 node를 가리키게 함
- 다음 노드 next를 반환
Node 클래스: popNext() 연산
def popNext (self): # self의 다음 노드를 삭제하는 연산
next = self.link # 현재 노드(self)의 다음 노드
if next is not None:
self.link = next.link
return next # 다음 노드를 반환
단순 연결 리스트 클래스의 데이터
머리 노드를 가리키는 변수 head
맨 처음에는 공백 상태가 되어야 하므로 생성자에서 head는 None으로 초기화
단순 연결 리스트 클래스 정의와 생성자
class LinkedList: # 단순 연결 리스트 클래스
def __init__(self): # 생성자
self.head = None # head 선언 및 None으로 초기화
단순 연결 리스트 클래스의 연산
공백 상태와 포화 상태를 검사하는 isEmpty()와 isFull() 연산
공백 상태: head가 None인 경우
연결된 구조에서는 메모리가 남아 있다면 언제든지 노드를 추가할 수 있음
→ 포화 상태: 절대 되지 않음 ⇒ 항상 False 반환
LinkedList 연산: 포화, 공백 상태 검사
def isEmpty(self): # 공백 상태 검사
return self.head == None # head가 None이면 공백
def isFull(self): # 포화 상태 검사
return False # 연결된 구조에서는 포화 상태 없음
pos번째 노드를 반환하는 getNode(pos) 연산
pos번째 요소를 구하기 위해 해당 요소가 들어 있는 노드를 찾음
pos가 유효하지 않은 위치라면 None을 반환
pos가 유효한 위치라면 머리 노드부터 링크를 따라 여러 번 이동해야 함
LinkedList 연산: getNode(pos)
def getNode(self, pos):
if pos < 0 : return None # 잘못된 위치 -> None
ptr = self.head # 시작 위치 -> head
for i in range(pos):
if ptr == None:
return None
ptr = ptr.link
return ptr # 최종 노드를 반환새로운 포인터 ptr이 맨 처음에 head를 가리키도록 한 다음, 링크를 따라 pos 번 이동하면 ptr이 원하는 노드를 가리키고 해당 노드를 반환하도록 구현
pos번째 요소를 반환하는 getEntry(pos) 연산
getNode(pos)로 pos번째 노드를 구하여 그 노드의 데이터를 반환하도록 함
LinkedList 연산: getEntry(pos)
def getEntry(self, pos):
node = self.getNode(pos) # pos번째 노드를 구함
if node == None: return None # 해당 노드가 없는 경우
else: return node.data # 있는 경우 데이터 필드 반환배열 구조와 getNode(pos)에서 pos번 이동이 필요한 것이 연결된 구조의 가장 큰 단점
pos 위치에 새로운 요소를 삽입하는 insert(pos, e) 연산
pos 위치에 새로운 노드를 삽입하려면 pos-1 위치의 노드(before)를 알아야 함
(삽입 과정에서 pos-1 노드의 링크가 변경되어야 하기 때문)
- 요소를 이용해 새로운 노드 node를 만듦
- pos-1 위치의 노드 before를 찾음
- before에 node를 추가
3. 은 노드의 append() 연산 이용
예외 상황: 2. 에서 찾은 before가 None인 경우 (삽입할 위치의 이전 노드가 없음)
→ 리스트의 맨 앞에 추가하려는 것. 연결 구조의 맨 앞에 새로운 노드를 넣음
→ 머리 노드가 변경되었으니 head 포인터가 수정되어야 함
LinkedList 연산: 삽입 연산 insert(pos, e)
def insert(self, pos, e):
node = Node(e, None) # 삽입할 새로운 노드를 만듦
before = self.getNode(pos-1) # 삽입할 위치 이전 노드 탐색
if before == None:
node.link = self.head
self.head = node
else: before.append(node) # 아닌 경우: before 뒤에 추가before 노드를 찾기 위해 getNode(pos-1) 수행 → pos 번의 이동 필요
pos 위치의 요소를 삭제하는 delete(pos) 연산
pos 위치에 있는 노드를 삭제하기 위해서도 pos-1 위치의 노드(before)를 알아야 함
(삭제 과정에서 pos-1 노드의 링크가 변경되어야 하기 때문)
- pos-1 위치의 노드 before를 찾음
- before의 다음 노드를 삭제
2. 는 노드의 popNext() 연산 이용
예외상황: before가 None인 경우 (리스트의 머리 노드를 삭제하는 상황)
→ head 포인터 수정
LinkedList 연산: 삭제 연산 delete(pos)
def delete(self, pos):
before = self.getNode(pos-1)
if before == None: # 이전 노드가 없는 경우 (헤더 노드를 지우려는 경우)
before = self.head # 리스트가 비어 있는 경우 before = None이 되고 None 반환
if self.head is not None: # 리스트가 비어 있지는 않은 지 확인
self.head = self.head.link # 다음 노드가 head가 되도록 수정
return before
else: return before.popNext() # before의 다음 노드 삭제
전체 요소의 수를 구하는 size() 연산
변수 ptr을 이용해 머리 노드에서부터 링크를 따라 전체 노드를 방문하여 노드의 개수를 구하여야 함
LinkedList 연산: 전체 요소의 수 size()
def size(self):
ptr = self.head
count = 0
while ptr is not None: # ptr이 None이 아닌 동안
ptr = ptr.link # 링크를 따라 ptr 이동
count += 1 # 이동할 때마다 count 증가
return count # count 반환
리스트를 보기 좋게 화면에 출력하는 display() 연산
모든 노드를 순서대로 방문하며 출력
LinkedList 연산: 화면 출력 display()
def display(self, msg='LinkedList:'):
print(msg, end='')
ptr = self.head
while ptr is not None:
print(ptr.data, end='->')
ptr = ptr.link
print('None')
연결 리스트와 파이썬 리스트 비교
LinkedList replace 연산 구현
def replace(self, pos, e):
node = self.getNode(pos)
if node == None: return None
else: node.data = e책에는 정의되어 있지 않아, 직접 구현해보았음
LinkedList와 파이썬 리스트 비교
# 단순 연결 리스트(LinkedList)
s = LinkedList()
s.display('연결리스트(초기): ')
s.insert(0, 10)
s.insert(0, 20)
s.insert(1, 30)
s.insert(s.size(), 40)
s.insert(2, 50)
s.display("연결리스트(삽입x5): ")
s.replace(2, 90)
s.display("연결리스트(교체x1): ")
s.delete(2)
s.delete(3)
s.delete(0)
s.display("연결리스트(삭제x3): ")
print("\n")
# 파이썬의 리스트
l = []
print('파이썬list(초기):', l)
l.insert(0, 10)
l.insert(0, 20)
l.insert(1, 30)
l.insert(len(l), 40)
l.insert(2, 50)
print('파이썬list(삽입x5):', l)
l[2] = 90
print('파이썬list(교체x1):', l)
l.pop(2)
l.pop(3)
l.pop(0)
print('파이썬list(삭제x3):', l)
< 실행 결과 >
03-6 이중 연결 구조로 리스트 구현하기
이중 연결 구조를 위한 노드 클래스
이중 연결 구조의 노드 클래스 정의와 생성자
이중 연결을 위해서는 이전 노드를 가리키는 prev와 다음 노드를 가리키는 next, 두 개의 링크가 필요
이중 연결 구조를 위한 DNode 클래스 정의
class DNode:
def __init__(self, elem, prev=None, next=None):
self.data = elem # 노드의 데이터 필드(요소)
self.next = next # 다음 노드를 위한 링크
self.prev = prev # 이전 노드를 위한 링크(추가됨)
꼬리 노드의 next는 반드시 None을 가리켜야 하고, 머리 노드의 prev도 None으로 처리
새로운 노드를 뒤에 추가하는 DNode 클래스의 append() 연산
- node의 next가 self.next를 가리키게 함
- node의 prev가 self를 가리키게 함
- node.next가 있으면, 이전 노드로 node를 가리키게 함
- self의 next가 node를 가리키게 함
DNode의 append(node) 연산
def append(self, node): # self 다음에 node를 넣는 연산
if node is not None: # node가 None이 아니면
node.next = self.next # 1.
node.prev = self # 2.
if node.next is not None: # 3. self의 다음 노드가 있으면
node.next.prev = node # 그 노드의 이전 노드는 node
self.next = node # 4.
다음 노드를 연결 구조에서 꺼내는 DNode 클래스의 popNext() 연산
self 뒤에 있는 node(self.link)를 꺼냄
- self의 next가 node의 next를 가리키게 함
- self의 next(기존 node.next였던 노드)가 있으면 self.next.prev가 self를 가리키게 함
DNode의 popNext() 연산
def popNext(self): # self 다음 노드 삭제 연산
node = self.next # 삭제할 노드
if node is not None: # next가 None이 아니면
self.next = node.next # 1.
if self.next is not None: # 2. 다음 노드가 있으면
self.next.prev = self # 그 노드의 이전 노드는 self
return node # 다음 노드를 반환
이중 연결 리스트 클래스
이중 연결 리스트 클래스 정의와 생성자
class DblinkedList: # 이중 연결 리스트 클래스
def __init__(self): # 생성자
self.head = None # head 선언 및 None으로 초기화
isEmpty(), isFull(), getEntry(pos)
isEmpty(), isFull(), getEntry() 등은 코드가 정혹히 동일
LinkedList의 getNode(), size(), display() 등의 연산에서 .link를 .next로 수정하면 이중 연결 리스트에서도 정확히 동작
DblLinkedList 연산: isEmpty(), isFull(), getNode(), getEntry(), size(), display(), replace()
def isEmpty(self): # 공백 상태 검사
return self.head == None # head가 None이면 공백
def isFull(self): # 포화 상태 검사
return False # 연결된 구조에서는 포화 상태 없음
def getNode(self, pos):
if pos < 0 : return None # 잘못된 위치 -> None
ptr = self.head # 시작 위치 -> head
for i in range(pos):
if ptr == None:
return None
ptr = ptr.next
return ptr # 최종 노드를 반환
def getEntry(self, pos):
node = self.getNode(pos) # pos번째 노드를 구함
if node == None: return None # 해당 노드가 없는 경우
else: return node.data # 있는 경우 데이터 필드 반환
def size(self):
ptr = self.head
count = 0
while ptr is not None: # ptr이 None이 아닌 동안
ptr = ptr.next # 링크를 따라 ptr 이동
count += 1 # 이동할 때마다 count 증가
return count # count 반환
def display(self, msg='DblLinkedList:'):
print(msg, end='')
ptr = self.head
while ptr is not None:
print(ptr.data, end='<=>') # 이중 연결은 <=>로 표시
ptr = ptr.next # 다음 노드로 이동
print('None')
def replace(self, pos, e):
node = self.getNode(pos)
if node == None: return None
else: node.data = e
pos 위치에 새로운 요소를 삽입하는 insert(pos, e) 연산
pos 위치에 삽입을 위해서는 pos-1 위치의 노드(before)를 찾아야 하는데 이중 연결 구조에서는 pos 위치의 노드를 찾더라도 prev 링크를 통해 pos-1번째 노드를 알 수 있음
DBLinkedList 연산: 삽입 연산
def insert(self, pos, e):
node = DNode(e)
before = self.getNode(pos-1) # 삽입할 위치 이전 노드 탐색
if before == None: # 머리 노드로 삽입하는 경우
node.next = self.head
if node.next is not None:
node.next.prev = node
self.head = node
else: before.append(node) # 아닌 경우: before 다음에 추가
pos 위치의 요소를 삭제하는 delete(pos) 연산
LinkedList와 대부분 코드가 동일하나 link가 아닌 next를 사용하고, 머리 노드를 삭제하는 경우 새로운 머리 노드의 이전 노드를 None으로 처리하는 부분만 다름
DBLinkedList 연산: 삭제 연산
def delete(self, pos):
before = self.getNode(pos-1)
if before == None: # 머리 노드 삭제 경우
before = self.head
if self.head is not None:
self.head = self.head.next
if self.head is not None:
self.head.prev = None
return before
else: before.popNext() # before의 다음 노드 삭제
이중 연결 리스트 클래스 테스트
# 이중 연결 리스트(DblLinkedList)
s = DblinkedList()
s.display('연결리스트(초기): ')
s.insert(0, 10)
s.insert(0, 20)
s.insert(1, 30)
s.insert(s.size(), 40)
s.insert(2, 50)
s.display("연결리스트(삽입x5): ")
s.replace(2, 90)
s.display("연결리스트(교체x1): ")
s.delete(2)
s.delete(3)
s.delete(0)
s.display("연결리스트(삭제x3): ")
<실행 결과>
'ECC - 알고리즘 > 자료구조와 알고리즘 with 파이썬' 카테고리의 다른 글
| Chapter07. 탐색 (0) | 2025.05.08 |
|---|---|
| Chapter06. 정렬 (0) | 2025.05.03 |
| Chapter04. 트리 (0) | 2025.04.01 |
| Chapter 02. 큐 (0) | 2025.03.21 |
| Chapter 01. 스택 (0) | 2025.03.19 |