사진: Unsplash의Lionello DelPiccolo
목차
- 리스트
- 노드
- 타입힌트
- 연결리스트 구현(생성자, 삽입, 검색)
__init__(),__len__()add_first()add_last()print()search()__contains__()
- 연결리스트 구현(삭제)
remove_first()remove_last()remove()remove_at()clear()
1. 리스트
- 리스트(list)는 순서가 있는 데이터를 나열한 구조
- 실생활의 예
- 학생 명단, 상점의 판매 품목, 실시간 금상승 검색어, 버킷 리스트 등
이미지 출처: 세종대 학술정보원
2. 노드
노드(node)
- 연결 리스트를 구성하는 각각의 원소
- 데이터와 포인터(뒤쪽 노드를 참조하고 있음)를 가짐
이미지 출처: gongsam21의 티스토리
노드 연결하기
- 자기 참조(self-referential)
- 자기 자신을 가리키는 화살표 - 참조: 목적지를 방향으로 가리키는 화살표
- Node 클래스의 속성(멤버변수)들
- data: 데이터에 대한 참조
-next- 뒤쪽 노드에 대한 참조,다음 데이터 그 자체를 의미하게 됨
- 뒤쪽 노드가 없다면 None('값이 없다')값이 됨
3. 타입힌트(type hint, annotation)
- 타입 힌트: 프로그래밍에서 자료형 관련 실수를 줄이기 위해 함수의 매개변수와 리턴 자료형을 명시하는 것.
- 일종의 주석으로 타입 힌트는 강제성이 없다.
- ⭐타입 힌트를 지키지 않더라도 문법적 에러가 발생하지 않는다.
타입 종류
-
Any: 모든 타입 -
int: 정수 -
float: 정수 또는 실수 -
str: 문자열 -
list: 리스트 -
⭐
list[int]: 정수를 원소로 가지는 리스트 -
list[str]: 문자열을 원소로 가지는 리스트 -
tuple: 튜플 -
⭐
tuple[int,str,int]: 정수, 문자열, 정수를 원소로 가지는 튜플
예) (2, "ABC", 14) -
dict: 딕셔너리 -
⭐
dict[str, int]: 키는 문자열 타입, 값은 정수형인 딕셔너리
예) {"abc": 1, "def":2}
Node 클래스 구현
-
노드 하나당 하나의 데이터를 가짐
-
아무 값도 안 넣으면 None이 기본값
-
next는 뒤에 붙은 node를 가리킴 -
next의 데이터 타입은 class로 정의한 Node
-
노드에 데이터를 입력한 뒤 노드끼리
next속성으로 연결해준다.
4. 연결리스트 구현(생성자, 삽입, 검색)
연결리스트
- 리스트를 구현하는 방법 중 하나
- 연결리스트는 각 노드가 데이터와 포인터를 가지고 한 줄로 연결되어있는 방식으로 데이터를 저장하는 자료 구조
- 머리 노드(head node): 연결리스트의 맨 앞에 있는 노두
- 꼬리 노드(tail node): 연결리스트의 맨 끝에 있는 노드
이미지 출처
속성
no: 리스트에 등록되어 있는 노드의 개수head: 머리노드에 대한 참조
메소드
__init__(): 생성자(초기화하는 함수)__len__(): 연결리스트의 노드 개수를 리턴하는 함수
- 호출 방법:len()
- no값을 리턴함
add_first: 맨 앞에 노드를 삽입하는 코드
- 머리노드에 새로운 노드 연결
- 기존 머리노드에 새로운 노드next로 연결
ptr = self.head기존 머리 노드를
ptr변수에 저장한다.
self.head = Node(data, ptr)머리노드를 'A'에서 ('G', 'A')로 변경했다. 'A'가 삭제되었다가 다시 두 번째 노드로 추가되었으므로 'G'노드가 새롭게 추가된 효과가 나타난다.
self.no += 1
self.no는 수동으로 기록해 주어야 하는 속성이다. 노드가 하나 추가되었으므로 개수도 1 더해준다.self.no = self.no + 1로도 쓸 수 있다.
add_last(): 맨 뒤에 노드를 삽입하는 함수
- 꼬리 노드를 찾고 꼬리노드 뒤에 새로운 노드를 삽입
if self.head is None: self.add_first(data)머리노드가
None이면self.head를 불러올 때 오류가 발생하므로if문을 통해 처리를 해준다. 빈 노드면 단순히 맨 앞에 노드를 삽입하기만 하면 된다.
else: ptr = self.head while ptr.next is not None: ptr = ptr.next ptr.next = Node(data) self.no += 1빈 노드가 아니면 머리노드를
ptr변수에 저장한 다음next가None일 때까지(노드가 끝날 때까지)ptr을next(이동)한 다음,ptr뒤에 새 노드를 추가해준다. 위에서와 마찬가지로self.no를 수동으로 카운트해준다.
print(): 연결리스트의 모든 노드들을 출력하는 함수
search(): 매개변수 data와 값이 같은 노드의 위치를 리턴하는 함수
__contains__(): 데이터 포함 여부를 판단하는 함수
5. 연결리스트 구현(삭제)
remove_first(): 머리 노드를 삭제하는 함수
- 리스트가 비어있지 않을 때(head is not None)만 머리노드 삭제
-head.next를 머리 노드에 대한 참조인head에 대입함
remove_last(): 꼬리 노드를 삭제하는 함수
- 리스트에 노드가 하나만 존재할 때 머리 노드를 삭제하는 것이므로remove_first()함수 호출
-리스트에 노드가 2개 이상 존재할 때 리스트의 맨 끝에서 노드 삭제
remove():p(어떤 노드건 선택 가능)가 지목하는 노드를 삭제하는 함수
- 리스트가 비어있지 않고 노드p가 존재할 경우
-p가 머리 노드면remove_first()호출
-p가 머리 노드가 아니면p이전 노드를 이용하여next값인p노드를 삭제
remove_at(): index에 위치한 노드를 삭제
- index -1의 위치를 찾은 다음- index 위치의 노드를 삭제
clear(): 모든 노드를 삭제하는 함수
- 연결 리스트가 비어있을 때까지 머리 노드의 삭제를 반복하여 모든 노드 삭제
