1. 리스트
■ 리스트(=선형 리스트(linear list))는 순서 또는 위치(position)를 가진 항목들이 차례대로 나열된 선형 자료구조이다.
■ 리스트를 기호로 표현하면 다음과 같다.
list = [item0, item1, item2, ... , item(n-1)]■ 항목간 중복을 허용하지 않고 순서가 없는 집합(set), 값의 변경이 불가능한 튜플과는 다르게 리스트는 이러한 제한이 없다.
■ 리스트 구조는 다음 그림과 같이 항목들이 순서대로 나열되며 인덱스라는 위치를 가진다.
■ 리스트처럼 선형 자료구조인 스텍, 큐, 덱은 항목에 대한 접근이 전단 혹은 후단으로 제한되지만, 리스트는 이런 제한이 없어서 어떤 위치에서든 항목의 삽입 혹은 삭제가 가능하다. 즉, 리스트는 선형 자료구조 중 항목의 삽입, 삭제가 가장 자유롭다고 할 수 있다.
1.1 리스트 메소드
5. Data Structures
This chapter describes some things you’ve learned about already in more detail, and adds some new things as well. More on Lists: The list data type has some more methods. Here are all of the method...
docs.python.org
1.2 리스트 구현
■ 리스트같은 어떠한 자료구조를 구현하기 위해 배열(array)구조와 연결된(linked) 구조를 이용할 수 있다.
1) 배열 구조
- 배열 구조로 만든 리스트를 선형 순차 리스트(linear sequential list), 순차 리스트, 리스트라고 한다.
- 배열 구조는 동일한 자료형의 데이터를 한꺼번에 생성할 때 사용한다.
- 배열의 항목에 접근하기 위해 인덱스 연산자인 '[ ]'를 사용한다. 예를 들어 A라는 배열이 있으면, 인덱스는 0부터 시작하므로 A[1]은 배열 A의 두 번째 항목을 나타낸다.
- 그리고 배열의 항목들은 메모리에서 연속적인 공간에 인덱스 순서대로 다음 그림처럼 위치한다.
따라서 배열 크기에 상관없이 원하는 항목을 바로 찾아갈 수 있다. 즉 항목 접근, 데이터를 불러오는 접근의 연산에 대한 시간 복잡도가 \( O(1) \)이다.
- 단점은 삽입 혹은 삭제 연산이 느리다는 점이다. 즉, 데이터를 넣고 빼는 등의 연산이 비효율적이다.
또한 항목의 개수, 즉 들어가는 항목의 개수가 제한되어 용량을 변경하기 어려울 수 있다.
2) 연결된 구조
- 연결된 구조는 다음 그림처럼 항목들을 링크로 연결하는 방법이다. 이때 서로 인접해 있는 항목이라도 메모리에서 인접한 위치에 있다는 보장이 없다.
이렇게 자료들을 일렬로 나열한 구조를 연결 리스트(linked list)라고 한다.
- 항목들을 모두 링크로 연결하다 보니, 모든 항목들은 링크를 통해 다음 항목의 위치만을 알고 있다.
- 이렇게 링크로 연결되기 때문에 크기에 제한이 없고, 삽입 혹은 삭제 연산이 배열 구조에 비해 효율적이다.
단, 위의 연결 리스트 그림처럼 배열 구조보다는 구현이 복잡하다는 점이 있다.
1.2.1 Linear Sequential List(선형 순차 리스트)
■ 컴퓨터 메모리에 자료의 저장이 순차적이므로, 항목 접근에 걸리는 연산의 수행 시간이 \( O(1) \)이다. 이때, 리스트 크기 n에 무관한 연산 시간이 소요된다.
- 논리적 순서와 메모리 저장된 순서가 일치한다.
- 예를 들어 C에서는 다음과 같이, 자료형 입력, 리스트 이름 입력, 몇 개의 항목이 들어가는지 명시, 그리고 이 선언들과 동시에 바로 항목을 넣어줄 수도 있다.
int Arr[4] = {1, 2, 3, 4}이렇게 정의하고 실행하면 컴퓨터에시 이 배열을 다음과 같이 저장한다.
cf) C 언어에서 int를 각각 표현하는데 4 byte가 사용된다. 즉, 하나의 int마다 4 byte 공간을 사용한다.
cf) 1 byte마다 메모리 주소가 1씩 올라간다.
■ 파이썬에서는 어떠한 변수를 선언할 때, 그 변수의 type을 선언하지 않는다.
python_list = [item0, item1, item2, ... ]■ 또한 파이썬 리스트는, 리스트 안에 들어가는 항목들의 자료형이 동일할 필요가 없다.
즉 서로 다른 type, 정수, 실수, 문자열, 튜플, 딕셔너리 등이 같은 리스트 안에 있을 수 있다.
■ 메모리에 저장 시 메모리 공간을 차지하는데 부여된 공간의 각각의 주소가 항목들을 나타낸다.
■ 예를 들어 윈도우 64 bit는 주소를 64 bit = 8 byte로 나타내므로,
- 만약, python_list = [item0, item1, item2, item3]일때, 첫 번째 항목인 item0을 꺼내고 싶다면 메모리상 리스트가 저장되어 있는 주소가 첫 번째 항목인 item0의 주소와 동일하므로 바로 접근하여 항목을 꺼낼 수 있다.
즉, 주소가 저장되어 있으니 바로 item0에 접근할 수 있다. 이렇게 첫 번째 항목을 꺼내는데 2번 정도의 연산(접근)이 필요하다.
- 만약 세 번째 항목을 보고 싶다면, 세 번째 항목이 저장된 주소에 접근해서 item2에 접근하면 된다.
이 주소를 계산하는 방법은, 첫 번째 주소가 a라고 하면 a + 8(byte) × 2를 하면 해당 주소가 나온다.
이렇게 item2를 나타내는 주소가 있으니, 이 주소를 통해 item2에 접근하면 된다. 마찬가지로 주소에 접근하고 item2를 꺼내는데 2번의 연산이 발생한다.
■ 이를 통해 알 수 있는 것은 첫 번째 항목을 찾든, 세 번째를 항목을 찾든, n - 1번째 항목을 찾든, 접근하는데 사용되는 연산 시간이 상수 시간으로 동일하다.
■ 즉, 리스트의 크기 n에 상관없이 자료에 접근하는 시간이 모든 항목에 동일하기 때문에 자료에 접근하는 알고리즘이 \( O(1) \)이다.
1.3 동적 배열
■ 파이썬 리스트는 동적 배열로 구현되어 있다.
■ 예를 들어 list = [1, 2, 3]일 때, 리스트의 크기가 3이고 리스트의 용량이 100이라고 했을 때, append(1)을 수행하면 공간이 여유가 있으므로 4를 네 번째 항목으로 추가할 수 있다. 추가되면 리스트의 크기는 4, 리스트의 용량은 100이다.
그리고 항목을 계속 추가해 리스트 크기와 리스트 용량이 모두 100이 된 상태(=남은 공간이 없는 상태)에서 append(10)을 수행하려면, 추가적인 공간이 필요하여 기존의 메모리를 모두 없애고 더 큰 새로운 메모리를 할당하여 사용하는데, 이것이 바로 동적 배열이다.
- 먼저 기존보다 용량이 더 큰 새로운 메모리를 할당하고, 기존 메모리에 저장된 모든 항목들을 이 새로운 메모레이 복사한다.
그리고 append(1000)으로 새로운 항목 1000을 추가한다. 그러면 기존 메모리는 해제되고 새로운 리스트는 새로운 메모리를 참조한다.
- 리스트의 크기와 리스트 용량이 100인 상태에서 새로운 항목이 추가되어 리스트 크기는 101이 되고, 리스트의 용량은 크기 101을 뺀 만큼의 여유 공간을 가지게 된다.
■ 이렇게 파이썬 리스트는 동적 배열의 개념을 이용해 리스트의 용량을 늘릴 수 있다. 그러나 여유 공간, 즉 그 만큼의 메모리 낭비가 발생한다.
cf) 튜플은 정적 배열로서 용량 변경이 불가능하다. 따라서 리스트보다 효율적으로 메모리를 사용할 수 있다.
그러므로 상황에 맞게, 데이터가 변경될 가능성이 있으면 리스트, 그렇지 않다면 튜플을 사용하면 된다.
1.4 파이썬 리스트 시간 복잡도
■ 자료에 접근하는 연산은 앞서 설명한 것처럼 대부분의 경우 \( O(1) \)이다.
■ append( )의 시간 복잡도는 상황별로 다르다.
- 1.3 동적 배열에서 본 것처럼, 리스트 용량에 여유가 있으면 바로 항목을 삽입할 수 있어 시간 복잡도는 \( O(1) \)이다.
- 그러나 용량을 늘려야 할 경우, 새로운 리스트를 메모리에 할당하고 기존 항목들을 모두 복사해야 하기 때문에 최소 \( O(n) \)의 시간이 소요된다.
■ 리스트 용량이 여유가 있는 경우, insert( )의 최악의 경우(worst)는 맨 앞에 항목을 삽입(=전단 삽입)하는 것이다.
- 배열 구조에서 맨 앞에 새로운 항목을 삽입하려면, 먼저 모든 항목들이 한 칸씩 뒤로 이동하고 0 번째 항목에 값이 들어오므로,리스트의 크기가 n이라면 총 n 번의 이동이 발생한다. 즉, 시간 복잡도는 \( O(n) \)이 된다.
■ 따라서 최선의 경우(best)는 후단 삽입이 된다.
-파이썬 리스트에서 맨 앞이나 중간에 새로운 항목을 삽입하는 것은 최악의 경우 n 번의 항목 이동이 발생하여 비효율적이지만, 새로운 항목을 리스트 맨 뒤에 삽입하는 것은 꽤 효율적이다.
■ 삭제 & 반환 연산인 pop( )도 마찬가지이다. 맨 앞의 항목이나 중간에 있는 항목을 삭제하는 것은 삭제한 항목 다음에 있는 모든 항목들이 앞으로 한 칸씩 이동하므로 비효율적이고, 맨 뒤의 항목을 삭제한다면 항목들이 앞으로 한 칸씩 이동할 필요가 없으므로 효율적이다.
■ 따라서 가능한 삽입은 리스트 맨 뒤에 항목을 추가하는 append( )를 사용하고, 삭제는 pop(-1)로 맨 뒤의 항목을 삭제하는 것이 좋다.
1.5 배열 구조로 리스트 구현
List and List ADT – Data structures (inflibnet.ac.in)
List and List ADT – Data structures
2 List and List ADT T.V. Geetha Welcome to the e-PG Pathshala Lecture Series on Data Structures.This is the second module of the paper and we will be talking about list and list ADT – a basic data structure.You will be studying list ADT and the different
ebooks.inflibnet.ac.in
■ 위와 같은 리스트 ADT 연산들을 파이썬의 리스트를 이용해 다음과 같이 구현할 수 있으며, 이외에도 리스트 항목의 값 바꾸기, 리스트 정렬, 리스트 병합 등을 구현할 수 있다.
class ArrayList:
def __init__(self):
self.items = []
def ListAppend(self, item):
self.items += [item]
def ListSize(self):
return len(self.items)
def ListIsEmpty(self):
return len(self.items) == 0
def ListInsert(self, pos, e):
self.items.insert(e, pos)
def ListDelete(self, e):
self.items.remove(e)
def ListFind(self, pos):
return self.items.index(pos)
def ListFindK(self, pos):
return self.items[pos]
def printList(self):
for i in self.items:
print(i, end = " ")
def ListMakeEmpty(self):
empty_list = []
self.items = empty_list.copy()
return self.items
def ListMakeEmpty2(self):
empty_list = []
self.items = copy.deepcopy(empty_list)
return self.items
def ListRemove(self, pos):
return self.items.pop(pos)
def ListReplace(self, pos, e):
self.items[pos] = e
def ListSort(self):
self.items.sort()
def ListMerge(self, iterable):
self.items.extend(iterable)a_list = ArrayList()
a_list.ListAppend(34)
a_list.ListAppend(12)
a_list.ListAppend(52)
a_list.ListAppend(16)
a_list.ListAppend(12)
a_list.items
```#결과#```
[34, 12, 52, 16, 12]
````````````print(a_list.ListSize())
```#결과#```
5
````````````print(a_list.ListIsEmpty())
```#결과#```
False
````````````- def ListIsEmpty(self): 는 if 문을 사용해 True, False를 반환해도 되지만, return len(self.items) == 0으로 할 경우, 조건문을 사용하지 않아도 문장 자체가 참이면 True, 거짓이면 False를 반환할 수 있다.
a_list.ListInsert(20, 3)
a_list.items
```#결과#```
[34, 12, 20, 16, 12]
````````````a_list.ListDelete(52)
a_list.items
```#결과#```
[34, 12, 20, 16, 12]
````````````a_list.ListFind(16)
```#결과#```
3
````````````
a_list.ListFindK(3)
```#결과#```
16
````````````a_list.printList()
```#결과#```
34 12 20 16 12
````````````a_list.ListRemove(4)
```#결과#```
12
````````````
a_list.items
```#결과#```
[34, 12, 20, 16]
````````````a_list.ListReplace(2, 52)
a_list.items
```#결과#```
[34, 12, 52, 16]
````````````a_list.ListSort()
a_list.items
```#결과#```
[12, 16, 34, 52]
````````````b = {'a':1,'b':2,'c':3}
a_list.ListMerge(b)
a_list.items
```#결과#```
[12, 16, 34, 52, 'a', 'b', 'c']
````````````
c = ['가','나','다']
a_list.ListMerge(c)
a_list.items
```#결과#```
[12, 16, 34, 52, 'a', 'b', 'c', '가', '나', '다']
````````````a_list.ListMakeEmpty()
```#결과#```
[]
````````````
a_list.items
```#결과#```
[]
````````````
a_list.ListAppend(34)
a_list.ListAppend(12)
a_list.ListAppend(52)
a_list.ListAppend(16)
a_list.ListAppend(12)
a_list.items
```#결과#```
[34, 12, 52, 16, 12]
````````````
import copy
a_list.ListMakeEmpty2() # copy 모듈을 이용한 깊은 복사
```#결과#```
[]
````````````
a_list.items
```#결과#```
[]
````````````
print(a_list.ListIsEmpty())
```#결과#```
True
````````````
1.6 Linked List
■ 각각의 데이터들이 다음 데이터를 기억하는, 즉 다음 순서를 기억하는 형태의 리스트를 링크드 리스트라고 한다.
■ 각 데이터들이 다음 순서인 데이터를 가리키는 화살표를 '링크(link)'라고 하며, 데이터와 링크를 묶어서 '노드(node)'라고 부른다. 이렇게 노드들이 연결되어 있는 방식으로 만든 것을 링크드 리스트라고 한다.
■ 노드는 데이터와 링크로 나눌 수 있으며, 데이터가 들어가는 부분을 '데이터 필드', 링크가 들어가는 부분을 '링크 필드'라고 한다. 그리고 첫 번째 노드를 가리키는 변수를 '헤드' 혹은 헤드 포인터(head pointer)'라고 한다.
■ 만약, 더 이상 다음 노드가 없으면 링크가 None, 즉 아무것도 가리키지 않는다.
■ 링크드 리스트의 종류는 단순 링크드 리스트와 원형 링크드 리스트, 이중 링크드 리스트가 있다.
1) 단순 링크드 리스트
2) 원형 링크드 리스트
- 더 이상 다음 노드가 없을 때, None이 아니라, 다시 첫 번째 노드를 가리키는 링크드 리스트이다.
3) 이중 링크드 리스트
- 각각의 노드가 다음의 노드와 직전의 노드를 가리키는 링크가 있어서 앞, 뒤로 접근이 가능한 링크드 리스트이다.
■ 앞서 배열 구조 리스트의 경우, 리스트 용량을 모두 사용하면 새로운 항목을 삽입할 때 번거로운 부분이 있었지만
연결된 구조인 링크드 리스트는 새로운 항목을 삽입할 때 데이터를 아무런 공간에나 저장한 다음, 기존의 마지막 노드에서 새로운 데이터로 링크만 이어주면 된다.
■ 즉, 배열 구조와 달리 용량이 고정되지 않는다는 특징이 있다. 따라서 데이터를 삽입하거나 삭제하는 것도 용이하다.
■ 예를 들어 New라는 항목을 배열 구조 리스트에 삽입 또는 삭제할 때, 리스트의 맨 마지막 항목 위에서 삽입 또는 마지막 항목을 삭제하는 것이 아니라면, 삽입되는 위치의 기존의 항목들을 모두 한 칸씩 뒤로 이동하거나, 삭제할 경우 한 칸씩 앞으로 이동해야 한다.
■ 반면, 링크드 리스트는 '링크'를 이용하면 배열 구조보다 삽입, 삭제를 수월하게 할 수 있다. 그러나 n 번째 항목에 접근하는데 \( O(n) \)의 시간이 걸린다.
■ 예를 들어
1) 링크드 리스트의 삽입은 다음 그림처럼 진행된다.
새로운 항목을 기존 C가 있던 위치인 세 번째 위치에 삽입하려면, 기존 B에서의 링크를 지우고, B에서 New에 링크를 이어주고, New의 링크를 C에 이어주면 된다.
2) 링크드 리스트의 삭제는 다음 그림처럼 진행된다.
위의 그림과 같이 C를 삭제하려면 기존에 C와 연견된 링크(B에서의 링크, C에서의 링크)를 모두 제거하고 B의 링크를 D에 연결하면 된다.
■ 따라서 이와 같이 삽입, 삭제할 위치를 정확히 알고 있다면 \( O(1) \)의 시간이 걸린다.
1.7 링크드 리스트 구현
■ 링크드 리스트는 노드들이 연결되어 있는 형태이므로, 먼저 노드를 구현하고, 이 노드를 이용해 전체적인 링크드 리스트를 구현해야 한다.
■ 노드는 데이터 필드와 링크 필드로 구성되어야 하며, 더 이상 다음 노드가 없다면 노드는 None을 가리켜야 한다.
class Node:
def __init__(self, data, link = None):
self.data = data # 데이터 필드
# 링크 필드
self.next_node = link # 노드가 하나 있는 상태이므로 더 이상 다음 노드가 없어 None을 가리켜야 함
def set_next(self, node): # 다음 노드를 설정하는 연산
self.next_node = node
def get_next(self):
return self.next_node # 다음 node를 반환하는 연산
def get_data(self):
return self.data
■ 링크드 리스트 구현에 있어 반드시 들어가야 하는 부분은 헤드 포인터(=헤드)를 초기화하는 연산이다. 따라서 이 부분은 다음과 같이 생성자 메소드로 구현하면 된다.
class LinkedList:
def __init__(self):
self.head = None # 아무것도 가리키지 않음. 즉, 아무것도 없는, 비어 있는 링크드 리스트이므로 None을 가리켜서
# 클래스 LinkedList로부터 객체를 만들었을 때 head에 None을 할당■ 이 외에 링크드 리스트가 비어 있는지 확인하는 메소드, 링크드 리스트의 항목들을 비우는 메소드, 그리고 노드에 접근하는 메소드를 다음과 같이 구현할 수 있다.
class LinkedList:
def __init__(self):
self.head = None # 아무것도 가리키지 않음. 즉, 아무것도 없는, 비어 있는 링크드 리스트이므로 None을 가리켜서
# 클래스 LinkedList로부터 객체를 만들었을 때 head에 None을 할당
def ListIsEmpty(self):
return self.head == None # 링크드 리스트가 비어 있는 경우 head의 값은 None이므로,
# head가 None이면(=비어 있으면) True, 그렇지 않으면 False를 반환하게 만들어서
# 링크드 리스트가 비어있는지 확인
def ListClear(self):
return self.head = None # 따라서 링크드 리스트를 비어 있게 만들려면 head에 None값을 할당하면 된다.
def get_node(self, pos): # pos >= 0이며 pos의 범위는 리스트 길이보다 크지 않다고 가정,그렇지 않으면 예외 발생
if pos >= 0:
curr = self.head # 먼저 헤드를 찾고
for i in range(pos):
curr = curr.get_next() # 헤드의 다음 node를 pos, 즉 지정된 위치에 따라 불러옴,
return curr #즉 링크드 리스트의 n 번째 노드에 접근하는 연산이다.
else:
raise Exception('pos의 값이 0 미만 입니다.')■ 링크드 리스트에서 노드 삽입은 insert 방식과 append 방식이 있다.
■ 먼저 append는 마지막 위치에 새로운 노드를 추가하거나 헤드가 비어 있는 경우, 헤드에 노드를 할당하면 된다.
def ListAppend(self, data):
if self.head == None: # 헤드가 비어 있는 경우
self.head = Node(data) # 새로운 노드를 만들고, 이 새로운 노드가 헤드가 된다.
return
curr = self.head # 헤드를 찾고
while curr.next_node is not None: # None을 가리키는 노드를 탐색, 즉 마지막 위치의 노드를 찾고
curr = curr.next_node
curr.next_node = Node(data) # 그 마지막 위치에 새로운 노드 추가■ insert는 원하는 특정 인덱스에 데이터를 넣어야 한다.
- 링크드 리스트에서는 첫 번째 자리, 즉 헤드에 삽입하는 경우와 원하는 위치에 삽입하는 경우로 나누어 고려한다면
- 헤드 위치에 새로운 노드를 삽입하는 경우, 삽입되는 새로운 노드는 기존의 헤드를 다음 노드로 링크해야 한다.
따라서 노드에서 다른 노드로 설정하는 set_next( ) 메소드로 기존의 헤드를 새로운 노드의 링크에 넣으면, 새로운 노드의 next_node는 기존의 헤드가 된다. 그리고 새로운 노드를 새로운 헤드로 지정해야 한다.
- 만약, 헤드가 아닌 다른 위치에 data를 삽입하려면, 삽입되는 위치의 기존의 링크를 제거하고 새로운 노드와 기존의 노드들을 연결해야 한다. 이렇게 하기 위해선 먼저 새로운 노드를 생선한 다음, 새로운 노드의 링크를 set_next( ) 메소드로 설정해야 한다.
- 따라서 새로운 노드를 만든 다음, 새로운 노드의 링크를 삽입할 임의의 위치 n의 노드에 이어주고, 위치가 n 바로 직전인 노드의 링크를 다음 그림처럼 새로운 노드에 연결시켜주면 된다.
def ListInsert(self, data, pos):
new_node = Node(data) # 먼저 새로운 노드를 만들고
if pos == 0: # 첫 번째 위치에 삽입하는 경우
new_node.set_next(self.head) # 새로운 노드의 다음 노드는 기존의 헤드
self.head = new_node # 그러면 새로운 노드가 새로운 헤드
else: # 임의의 위치 n에 삽입하는 경우
prev = self.get_node(pos-1) # pos가 n-1인 노드를 먼저 찾고
new_node.set_next(prev.get_next()) # prev.get_next()는 기존의 n-1 노드의 다음 노드,
# 즉 새로운 노드가 n에 위치하게 되어, 원래 위치 n에서 n + 1가 된 노드
# 이 n+1 노드는 pos가 n인 새로운 노드의 다음 노드
prev.set_next(new_node) # pos가 n-1인 노드의 다음 노드는 pos가 n인 새로운 노드■ 링크드 리스에서 노드를 삭제하는 연산도 첫 번째 노드인 헤드 노드를 삭제하는 경우와 헤드가 아닌 임의의 위치 n에 있는 노드를 삭제하는 경우로 나누어 고려해야 한다.
■ 먼저, 헤드를 삭제하는 경우 기존의 헤드 다음의 노드를 새로운 헤드로 설정하면 된다.
■ 만약, 헤드가 아닌 임의의 위치에 있는 노드를 삭제하려면, 삭제가 되는 위치 n의 노드의 직전 노드(위치가 n - 1인 노드)와 삭제가 되는 위치 n의 다음 노드(위치가 n + 1인 노드)를 이어주면 된다.
def ListRemove(self, pos):
if pos == 0: # 헤드를 삭제할 경우
self.head = self.head.get_next() # 기존 헤드의 다음 노드가 새로운 헤드가 된다.
else: # 헤드가 아닌 임의의 위치 n에 있는 노드를 삭제할 경우
prev = self.get_node(pos-1)
prev.set_next(prev.get_next().get_next()) # pos가 n-1인 노드의 다음 노드는 pos가 n+1인 노드이다.■ 만약, 링크드 리스트의 크기(size)를 확인하고 싶다면,
- 파이썬 리스트는 리스트의 사이즈를 확인하기 위해 len 함수를 사용하는데, len 함수의 작동 방식은 리스트 내의 첫 번째 항목부터 다음 항목이 없을 때까지(=마지막 항목까지) 함수의 개수를 모두 센 다음, 이 개수를 반환하는 것으로 볼 수 있다.- 이러한 작동 방식과 유사하게 링크드 리스트도 헤드 노드부터 다음 노드가 있는지 없는지 확인하며, 다음 노드가 있으면 다시 그 다음 노드의 다음 노드로 넘어가면서, 하나씩 count를 더해주면 된다.
def ListSize(self):
node = self.head # 첫 번째 노드인 헤드
count = 0
while True:
if node == None: # 링크드 리스트가 비어 있으면 count = 0이 된다.
break
count += 1 # 비어 있지 않으면 다음 노드로 넘어갈 때 마다 count + 1
node = node.get_next()
return count■ 이외에도 특정 위치의 노드를 확인하거나, 모든 노드를 출력하고 싶다면, 다음과 같이 헤드에서 시작하여 다음 노드로 넘어가면서 원하는 위치의 노드를 반환하거나 모든 노드를 출력할 수 있다.
def ListSearch(self, pos):
node = self.head
for i in range(pos):
node = node.next_node
return node
def ListShow(self):
curr = self.head
while curr is not None:
print(curr.data, end = " ")
curr = curr.next_node
## 코드를 정리하면
class LinkedList:
def __init__(self):
self.head = None
def ListIsEmpty(self):
return self.head == None
def ListClear(self):
self.head = None
def get_node(self, pos):
if pos >= 0:
curr = self.head
for i in range(pos):
curr = curr.get_next()
return curr
else:
raise Exception('pos의 값이 0 미만 입니다.')
def ListAppend(self, data):
if self.head == None:
self.head = Node(data)
return
curr = self.head
while curr.next_node is not None:
curr = curr.next_node
curr.next_node = Node(data)
def ListInsert(self, data, pos):
new_node = Node(data)
if pos == 0:
new_node.set_next(self.head)
self.head = new_node
else:
prev = self.get_node(pos-1)
new_node.set_next(prev.get_next())
prev.set_next(new_node)
def ListRemove(self, pos):
if pos == 0:
self.head = self.head.get_next()
else:
prev = self.get_node(pos-1)
prev.set_next(prev.get_next().get_next())
def ListSize(self):
node = self.head
count = 0
while True:
if node == None:
break
count += 1
node = node.get_next()
return count
def ListSearch(self, pos):
node = self.head
for i in range(pos):
node = node.next_node
return node
def ListShow(self):
curr = self.head
while curr is not None:
print(curr.data, end = " ")
curr = curr.next_nodeb_list = LinkedList()
print(b_list.head)
print(b_list.ListShow())
print(b_list.ListIsEmpty())
```#결과#```
None
None
True
````````````b_list.ListAppend(7)
print(b_list.head.get_data()) # 현재 링크드 리스트의 head의 data는 7
print(b_list.ListShow()) # 7 -> None 인 상태
```#결과#```
7
7 None
````````````b_list.ListAppend(3)
b_list.ListAppend(5)
b_list.ListAppend(10)
b_list.ListAppend(13)
print(b_list.ListShow()) # 7 -> 3 -> 5 -> 10 -> 13 -> None 인 상태
```#결과#```
7 3 5 10 13 None
````````````b_list.ListInsert(99, 3)
print(b_list.ListShow()) # 7 -> 3 -> 5 -> 99 -> 10 -> 13 -> None 인 상태
print(b_list.ListSearch(3).get_data()) # pos = 3인 노드의 데이터는 99
```#결과#```
7 3 5 99 10 13 None
99
````````````node_at_pos_3 = b_list.ListSearch(3)
print(node_at_pos_3.get_next().get_data()) # 데이터가 99인 노드 다음 순서의 노드의 데이터는 10,
# 이렇게 링크드 리스트는 다음 순서의 노드를 기억하고 있음
```#결과#```
10
````````````print(b_list.ListIsEmpty())
print(b_list.ListSize()) # 7 -> 3 -> 5 -> 99 -> 10 -> 13 -> None 인 상태
```#결과#```
False
6
````````````print(b_list.get_node(-1)) # 예외 발생
```#결과#```
Exception Traceback (most recent call last)
Cell In[216], line 1
----> 1 print(b_list.get_node(-1))
Cell In[200], line 18, in LinkedList.get_node(self, pos)
16 return curr
17 else:
---> 18 raise Exception('pos의 값이 0 미만 입니다.')
Exception: pos의 값이 0 미만 입니다.
`````````````print(b_list.get_node(0).get_data(), b_list.get_node(3).get_data())
```#결과#```
7 99
````````````
b_list.ListRemove(0) # 기존 헤드 7이 삭제되고 새로운 헤드는 3
b_list.ListRemove(2) # 3 -> 5 -> 10 -> 13 -> None인 상태
print(b_list.ListShow())
```#결과#```
3 5 10 13 None
````````````
b_list.ListClear() # 리스트 비우기
print(b_list.ListSize())
print(b_list.ListIsEmpty())
print(b_list.ListShow())
```#결과#```
0
True
None
```````````'자료구조' 카테고리의 다른 글
| 큐(Queue) (2) (0) | 2024.09.20 |
|---|---|
| 큐(Queue) (0) | 2024.09.18 |
| 스택(Stack) (0) | 2024.09.10 |
| 파이썬 (0) | 2024.09.03 |
| 자료구조와 알고리즘 (0) | 2024.08.28 |
