연결 리스트 (Linked List) 1 - 객체 구조

연결 리스트의 객체 구조

앞서 언급했듯이, 리스트의 하부 구조는 배열로 이루어져 있어서, 다음 두 가지와 같은 단점이 존재한다. 

1. 배열의 크기는 고정되어 있어서 배열이 크기 이상으로 삽입될 경우, 더 큰 배열을 할당받아 원소를 모두 옮겨주는 작업을 진행해야함

2. 원소를 삽입 또는 삭제하려면 일부 또는 원소 전부를 한 칸씩 시프트하는 불편함이 존재한다.'

 

연결 리스트(Linked List)는 배열의 공간 낭비를 피할 수 있는 자료구조이다. 원소가 추가 될 때마다 공간을 할당받아 추가하는 동적 할당 방식을 따른다. 

 

연결 리스트의 노드 구성

 

item : 정수나 실수 같은 숫자 타입이나 복잡한 객체가 저장 필드

next : 다음 노드를 가리키는 링크

 

연결 리스트의 일반적인 형태

__head : 첫 번째 노드를 가리키는 레퍼런스

각 노드들은 첫 번째 노드에서 링크를 따라 접근하며, 맨 마지막 노드의 링크는 뒤에 더 이상 노드가 없다는 의미로 None 값을 할당한다. 빈 노드의 경우에는 __head가 None 값을 갖고 있다.

※ 파이썬에서 언더바 2(__)개로 시작하는 필드나 메서드는 객체 내부에서만 사용된다는 뜻이다. -> 프라이빗 필드 또는 프라이빗 메서드라 부른다. (Private, Private Method)

 

연결 리스트의 작업

__head 첫 번재 노드에 대한 레퍼런스
__numItems 연결 리스트에 들어 있는 원소의 총 수

insert(i,x) x를 연결 리스트의 i번 원소로 삽입
append(x) 원소 x를 연결 리스트의 맨 뒤에 추가 
pop(i) 연결 리스트의 i번 원소를 삭제하면서 알려줌 
remove(x) 연결 리스트에서 (처음으로 나오는) x를 삭제
get(x) 연결 리스트의 i번째 원소 알려줌
index(x) 원소 x가 연결 리스트의 몇 번 원소인지 알려줌 
clear() 연결 리스트 전부 비우기
count(x) 연결 리스트에서 원소 x가 몇 번 나타나는지 알려줌
isEmpty() 연결 리스트가 빈 리스트인지 알려줌
size(0) 연결 리스트의 총 원소 수를 알려줌
extend(a) 연결 리스트에 iterable한 객체를 전부 추가
copy() 연결 리스트를 복사해서 새 연결 리스트를 리턴
reverse() 연결 리스트의 순서를 역으로 뒤집는다.
sort() 연결 리스트를 정렬한다.