728x90
반응형
본 포스트는 필자가 학습하고 작성한 글이기 때문에 틀린 내용이 있을 수 있습니다.
참고 : https://hudi.blog/ds-linked-list/
1. Array와 List
배열(Array)와 리스트(List)의 컴퓨터 공학적 개념을 먼저 알고 가자.
1.1. Array
- 고정된 크기를 가짐
- 메모리에 연속적인 공간을 할당받아 데이터를 저장
- 인덱스를 통해 데이터 접근이 빠름
- 중간의 있는 원소들의 삽입/삭제가 느림
삽입/삭제 후 뒤에있는 모든 원소들의 자리를 변경해줘야 하기 때문
1.2. List
- 동적인 크기를 가짐
- 각 원소는 다음 원소를 가리키는 포인터(Pointer)로 순서를 구현
- 크기 변경, 데이터 삽입/삭제 등이 용이
- 구현 방식에 따라 데이터 접근 속도가 배열보다 느릴 수 있음
1.3. Python에서의 List
- Python에서 사용되는 List는 위에서 설명한 'Array'로서 구현되어 있음
- 실제 메모리 공간에 모든 원소를 연속적으로 배치함. 따라서 인덱스로 원소에 접근 가능
- 단, 길이가 고정되어있지 않아 데이터의 추가, 삭제가 편리함
2. 연결 리스트 (Linked List) 개요
링크드 리스트는 각각의 데이터가 그 다음 데이터를 가리키는 방식으로 순서를 구현한다.
2.1. 노드 (Node)
- 연결 리스트의 기본 단위. 각 노드는 두 부분으로 구성되어 있음
- 데이터 (Data) : 실제 값
- 포인터 (Pointer) : 다음 노드를 가리킴
2.2. 종류
- 단일 연결 리스트 (Singly Linked List) : 각 노드가 데이터와 포인터 하나로 구성
- 이중 연결 리스트 (Doubly Linked List) : 각 노드가 데이터와 두 개의 포인터(이전 노드, 이후 노드)로 구성
- 원형 연결 리스트 (Circular Linked List) : 마지막 노드가 첫번째 노드를 가리킴
2.3. 장점
- 동적 크기 : 연결 리스트의 크기는 동적으로 변경될 수 있음
- 삽입/삭제 효율성 : 중간에 노드를 삽입하거나 삭제하는 것이 배열보다 효율적
2.4. 단점
- 임의 접근 : 배열과 달리 연결 리스트는 O(n)의 시간이 필요하므로 임의 접근이 비효율적
- 메모리 오버헤드 : 각 노드마다 추가적인 포인터 정보를 저장해야 하므로 추가적인 메모리 사용
2.5. Array 와 Linked List
3. 구현
이 포스터에서는 단일 연결 리스트를 구현한다. 이중 연결 리스트나 원형 리스트는 구성만 조금 바꿔주면 만들 수 있다.
3.1. Node 정의
<python />
class Node:
def __init__(self, data, next=None):
self.data = data
self.next = next
- 각 노드는 data와 다음 노드를 가리키는 포인터인 next를 맴버 변수로 가지고 있다.
3.2. LinkedList 정의
<python />
class LinkedList:
def __init__(self):
self.no = 0 # 링크드 리스트의 길이
self.head = None # 머리 노드
self.current = None # 이터레이터에서 사용될 변수
# print 했을 때 str로 반환
def __str__(self):
pointer = self.head
if pointer is None:
return ''
result = ''
while pointer is not None:
result += f'{pointer.data} → '
pointer = pointer.next
return result.rstrip(' → ')
- 단순 구현만 하려면 __init__만 정의하면 된다.
연결 리스트의 길이인 no, 머리 노드를 가리키는 head, 현재 위치를 가리키는 current를 맴버 변수로 정의. - __str__ 메서드는 해당 클래스의 인스턴스가 `print()`와 함께 사용될 때 str형태로 리턴한다.
여기서는 각 노드의 data 값과 다음 노드를 가리키는 pointer를 → 로 나타냈다.
3.3. add_first, add_last, __len__ 메서드 구현
<python />
class LinkedList:
...
def add_first(self, data):
"""첫번째 위치에 노드를 추가"""
pointer = self.head
self.head = Node(data, pointer)
self.no += 1
def add_last(self, data):
"""마지막 위치에 노드를 추가"""
pointer = self.head
if pointer is None:
self.add_first(data)
return
while pointer.next is not None:
pointer = pointer.next
pointer.next = Node(data, None)
self.no += 1
# len()에서 동작하게 해줌
def __len__(self):
return self.no
- add_first 메서드는 포인터에 기존의 머리 노드를 지칭하고 머리 노드에 새로운 노드를 추가한다.
이 때 data에 입력값을, next에 포인터를 넣어준다. - add_last 메서드는 head가 없다면 add_first를 실행하고 있다면 꼬리 노드까지 간 후
꼬리 노드 포인터에 새 노드를 연결해준다. - __len__ 메서드는 해당 클래스의 인스턴스가 `len()`과 함께 사용될 때 리턴값을 설정해준다.
여기서는 no 변수를 리턴.
3.4. remove_first, remove_last 메서드 구현
<python />
class LinkedList:
...
def remove_first(self):
if self.head is not None:
self.head = self.head.next
self.no -= 1
def remove_last(self):
if self.head.next is None:
self.remove_first()
else:
cur_pointer = self.head
pre_pointer = self.head
while cur_pointer.next is not None:
pre_pointer = cur_pointer
cur_pointer = cur_pointer.next
pre_pointer.next = None
self.no -= 1
- remove_first 메서드는 머리 노드를 두번째 노드로 지정하면 첫번째 노드의 연결이 끊기는 것으로 구현한다.
- remove_last 메서드는 꼬리 노드 전 노드의 포인터를 None으로 설정해 마지막 노드의 연결이 끊기는 것으로 구현한다.
3.5. append, remove 메서드 구현
<python />
class LinkedList:
...
def append(self, data):
self.add_last(data)
def remove(self, data):
if self.head is not None:
if self.head.data == data:
self.remove_first()
return True
pointer = self.head
while pointer.next is not None:
if pointer.next.data == data:
pointer.next = pointer.next.next
return True
pointer = pointer.next
return False
- append 메서드는 add_last와 역할이 동일
- remove 메서드는 입력값과 같은 첫번째 노드를 찾고 지운 후 True를 리턴, 없다면 False를 리턴
3.6. search, __contain__ 메서드 구현
<python />
class LinkedList:
...
def search(self, data):
"""입력값과 같은 첫번째 요소의 위치를 리턴하고, 없을 시 -1을 리턴"""
count = 0
pointer = self.head
while pointer is not None:
if pointer.data == data:
return count
count += 1
pointer = pointer.next
return -1
# in 에서 동작하게 해줌
def __contains__(self, data):
return True if self.search(data) >= 0 else False
- search 메서드는 노드를 선형 탐색하고, 입력값과 같은 첫번째 요소의 위치를 리턴한다.
꼬리 노드까지 탐색했는데도 발견되지 않았다면 -1을 반환한다 - __contains__ 메서드는 해당 클래스의 인스턴스가 `in` 키워드와 함께 사용될 때의 리턴값을 제어 가능.
여기서는 입력값을 search에 전달하고 해당 값이 있다면 True, 없다면 False를 리턴한다.
3.7. popleft, pop 메서드 구현
<python />
class LinkedList:
...
def popleft(self):
if self.head is not None:
data = self.head.data
self.head = self.head.next
self.no -= 1
return data
def pop(self):
if self.head.next is None:
data = self.popleft()
else:
cur_pointer = self.head
pre_pointer = self.head
while cur_pointer.next is not None:
pre_pointer = cur_pointer
cur_pointer = cur_pointer.next
data = cur_pointer.data
pre_pointer.next = None
self.no -= 1
return data
- popleft 메서드는 두번째 노드를 새로운 머리 노드로 지정하고 기존 머리 노드의 값을 리턴
- pop 메서드는 꼬리 노드 전 노드의 포인터를 None으로 하고 기존 꼬리 노드의 값을 리턴
3.8. 이터레이터 (Iterator) 구현
<python />
class LinkedList:
...
# iterator로 만들기 위한 메서드
def __iter__(self):
self.current = self.head
return self
# itertator로 만들었을 때 다음 요소를 알려주거나 중단함
def __next__(self):
if self.current is None:
raise StopIteration
else:
data = self.current.data
self.current = self.current.next
return data
연결 리스트도 순서가 있기에 반복 가능한 객체(Iterable)이다. 즉, 이터레이터로 만들 수 있다.
- __iter__ 메서드는 해당 클래스의 인스턴스를 이터레이터로 만들어준다.
- __next__ 메서드는 이터레이터로 만들었을 때 다음 요소를 알려주거나 중단해준다.
3.9. 검증
<python />
linked_list = LinkedList()
for i in [1,2,3,4,5]:
linked_list.add_last(i)
print('add last 1,2,3,4,5 : ', linked_list)
linked_list.append(6)
print('append 6 : ', linked_list)
linked_list.add_first(0)
print('add first 0 : ', linked_list)
print('len : ', len(linked_list))
print('current linked_list : ', linked_list)
print('serch 3 : ', linked_list.search(3))
print('serch 7 : ', linked_list.search(7))
print('current linked_list : ', linked_list)
print('3 in : ', 3 in linked_list)
print('7 in : ', 7 in linked_list)
linked_list.remove_first()
print('remove first : ', linked_list)
linked_list.remove_last()
print('remove last : ', linked_list)
print('remove 3 : ', linked_list.remove(3))
print('remove 6 : ', linked_list.remove(6))
print('current linked_list : ', linked_list)
print('popleft ', linked_list.popleft())
print('pop ', linked_list.pop())
print('current linked_list : ', linked_list)
print('for i in linked_list:')
for i in linked_list:
print(i)
728x90
반응형
