파이썬 선형 자료구조(배열/선형 리스트, 연결 리스트)

배열

 

1) 배열의 성질

• 배열은 메모리 상에 원소를 연속하게 배치한 자료구조이라서 k번째 원소의 위치를 바로 계산할 수 있다. k번째 원소를 O(1)에 확인하거나 변경할 수 있다. 임의의 위치에 원소를 추가, 제거하는 과정은 O(N)이다.
• 메모리는 다른 자료구조와 다르게 추가적으로 소모되는 메모리의 양(=overhead)이 거의 없다.
• 메모리 상에 데이터들이 붙어있어 Cache hit rate가 높다.
• 메모리 상에 연속한 구간이 필요해서 할당에서 다소 제약이 있다.

---

2) 파이썬 배열
우선, 기본 파이썬에는 다른 프로그래밍 언어에서 정의되는 배열이라는 것이 없다. 대신 데이터 분석 등에서 수치 해석을 위해 사용하는 넘파이 라이브러리에서 배열을 지원한다. 그래서, 파이썬의 리스트가 동적 배열의 특징을 갖고 있다.

• 가변적인 크기(초기값을 작게 잡고 필요하면 리사이징 됨)
• 인덱스를 통해 해당 원소에 바로 접근 가능

---

선형 리스트

 

1) 파이썬 리스트
동적 배열의 특징을 갖고 있고, 다른 타입의 자료형을 같이 저장할 수 있는 특징도 있다.

list = [0,'string',[1,5,6],True]

 

2) 파이썬 선형 리스트 구현

linearL = [] # 저장할 배열

def add_data(data): # 선형리스트 생성 함수
    inearL.append(None)
    lLen = len(linearL)
    linearL[lLen-1] = data
    
add_data('1')
add_data('2')
add_data('3')

def insert_data(position, data): # 데이터 삽입 함수
    linearL.append(None)
    lLen = len(linearL)
    ''' position을 삽입 위치라고 생각하고 쓴 코드
    for i in range(1,lLen-position,1)
        linearL[lLen-i] = linearL[lLen-(i+1)]
    linearL[position-1] = data
    '''
    # position이 인덱스 위치일 때
    for i in range(lLen-1, position, -1):
        linearL[i] = linearL[i-1]
        linearL[i-1] = None
    linearL[position] = data

def delete_data(position): # 데이터 삭제 함수

 

---

연결 리스트 : 원소들을 저장할 때 그 다음 원소가 있는 위치를 포함시키는 방식으로 저장하는 자료구조

 

1) 연결 리스트의 성질

• k번째 원소를 O(k)에 확인하거나 변경할 수 있다. 임의의 위치에 원소를 추가, 제거하는 과정은 O(1)이다.( 배열처럼 그 뒤의 원소들을 전부 옮기는 작업을 할 필요가 없고 다음 원소의 주소만 변경을 해주면 되기 때문에/ 단, 추가하고 싶은 위치의 주소를 알고 있을 경우에만 O(1). 만약 주소를 준 것이 아니라 원소를 세 번째 원소 뒤에 추가하라는 명령의 경우에는, 세 번째 원소까지 찾아가야 하는 시간이 추가로 걸려서 O(1)이라고 말할 수 없다. )
• 메모리 상에 데이터들이 연속해있지 않아 Cache hit rate가 낮지만 할당이 다소 쉬움.
• 추가적으로 필요한 공간 O(N)

2) 연결 리스트의 종류

• 단일 연결 리스트
• 이중 연결 리스트
• 원형 연결 리스트

기타) 연결 리스트  자료구조를 사용하는 경우

글자를 추가하거나 글자를 지우는 명령을 계속 수행해야 하는  경우에 배열은 임의의 위치에 글자를 추가하는 연산이 비효율적인데 연결 리스트에서는 O(1)에 처리할 수 있어서 연결 리스트로 구현할 경우에 효율적일 수 있다.

임의의 위치에서 원소를 추가하거나 임의 위치의 원소를 제거하는 연산을 많이 해야 할 경우에는 연결 리스트의 사용을 고려하자.

 

3) 연결 리스트 구현

cf) (파이썬의 경우)  기본 자료형인 리스트 자료형이 연결 리스트의 기능을 포함한다.