리스트

• 줄 세워져 있는 데이터
• 파이썬은 리스트를 기본 자료구조로 제공한다.

리스트의 작업

• i번 자리에 원소 x를 삽입한다.
• i번 원소를 삭제한다.
• 원소 x를 삭제한다.
• i번 원소를 알려준다.
• 원소 x가 몇 번 원소인지 알려준다.
• 리스트의 사이즈(원소의 총 수)를 알려준다.

배열 리스트

• 파이썬 기본 제공

• insert(i, x) 🠔 i번 자리에 원소 x를 삽입한다. (맨 앞자리 0번)
• append(x) 🠔 원소 x를 리스트의 맨 뒤에 추가한다.
• pop(i) 🠔 리스트의 i번 원소를 삭제하면서 알려준다.
• remove(x) 🠔 리스트에서 (처음으로 나타나는) x를 삭제한다.
• index(x) 🠔 원소 x가 리스트의 몇 번 원소인지 알려준다.
• clear() 🠔 리스트를 깨끗이 청소한다.
• count(x) 🠔 리스트에서 원소 x가 몇 번 나타나는지 알려준다.
• extend(a) 🠔 리스트에 나열할 수 있는 객체 a를 풀어서 추가한다.
• copy() 🠔 리스트를 복사한다.
• reverse() 🠔 리스트의 순서를 역으로 뒤집는다.
• sort() 🠔 리스트의 원소들을 정렬한다.

사용 예

list = []
list.insert(0, 'test')
list.insert(0, 'sample')
list.insert(1, 'mid')
list.append('end')
print(list)

>>> ['sample', 'mid', 'test', 'end']

파이썬 내장 리스트의 한계

• 배열로 구현되어 있으므로 배열의 한계를 거의 그대로 가진다.
• 원소 삽입 시 삽입하는 자리 오른쪽부터 끝까지 모든 원소를 한 칸씩 시프트해주는 부담
• 삭제에서는 반대 반향으로 시프트가 발생한다.
• 배열은 공간의 크기를 미리 정해서 받을 수 밖에 없다.
  • 받아놓은 공간이 꽉 차 있는 상태에서 삽입이 시도되면 배열의 한계를넘습니다.
  • 파이썬은 이럴 경우에 자동으로 더 큰 배열을 생성하고 기존 배열을 새 배열로 복사합니다.
    • 작업 부담이 큽니다.

연결 리스트

• 리스트는 하부 구조로 배열을 사용할 경우 미리 공간을 확보해두고 시작해야 합니다.
• 리스트에 원소가 궁극적으로 얼마나 들어올지 예상하기는 쉽지 않아 많든 적든 공간 낭비가 불가피합니다.
• 연결 리스트가 이를 회피합니다.
  • 원소가 추가될 때 마다 공간을 할당받아 추가하는 동적 할당 방식

• __head 🠔 첫 번째 노드에 대한 레퍼런스
• __numItems 🠔 연결 리스트에 들어 있는 원소의 총 수
  
  
• insert(i, x) 🠔 i번 자리에 원소 x를 삽입한다. (맨 앞자리 0번)
• append(x) 🠔 원소 x를 연결 리스트의 맨 뒤에 추가한다.
• pop(i) 🠔 연결 리스트의 i번 원소를 삭제하면서 알려준다.
• remove(x) 🠔 연결 리스트에서 (처음으로 나타나는) x를 삭제한다.
• get(i) 🠔 연결 리스트의 i번 원소를 알려준다.
• index(x) 🠔 원소 x가 리스트의 몇 번 원소인지 알려준다.
• isEmpty() 🠔 연결 리스트가 빈 리스트인지 알려준다.
• size() 🠔 연결 리스트의 총 원소 수를 알려준다.
• clear() 🠔 연결 리스트를 깨끗이 청소한다.
• count(x) 🠔 연결 리스트에서 원소 x가 몇 번 나타나는지 알려준다.
• extend(a) 🠔 연결 리스트에 나열할 수 있는 객체 a를 풀어서 추가한다.
• copy() 🠔 연결 리스트를 복사한다.
• reverse() 🠔 연결 리스트의 순서를 역으로 뒤집는다.
• sort() 🠔 연결 리스트의 원소들을 정렬한다.

배열 리스트와 연결 리스트의 비교

• 배열 리스트는 시작부터 고정된 크기를 지정합니다.

• 연결 리스트는 원소가 들어오는 대로 공간을 할당받아 넣습니다.
  
  

• 배열 리스트는 연속된 공간에 원소를 저장합니다

• 연결 리스트는 공간의 연속성이 없습니다.
  
  

• 배열 리스트는 다음 원소에 대한 링크가 없습니다.

• 연결 리스트는 다음 원소의 링크를 위한 공간이 추가로 필요합니다.
  
  

• 배열 리스트외 연결 리스트 둘 다 검색 시 평균 Θ(n)의 시간이 걸립니다.

  • 원소들이 크기순으로 정렬되어 있는 경우라면 배열 리스트에서 최악에 경우에도 Θ(log n) 시간에 검색이 가능합니다.

    • 이진 탐색 알고리즘

  • 원소들이 크기순으로 정렬되어 있는 경우라면 연결 리스트에서 최악에 경우에도 Θ(n) 시간에 검색이 가능합니다.
    
    

개선 및 확장

• 원형 연결 리스트
  • 연결 리스트에 있는 마지막 노드의 링크가 None값을 가지는 구조에서는 첫 노드와 마지막 노드에 대한 접근성이 극적으로 차이가 난다.
  • 이렇게 되면
    원소 수가 n이라면 원소를 맨 앞에 삽입/삭제할 때는 상수 시간(Θ(1))이 드는 반면, 맨 끝에 삽입/삭제할 때는 Θ(n)시간이 든다.
  • 해결법 :
    • 마지막 노드가 첫 번째 노드를 링크하도록 바꾼다.

• 양방향 연결 리스트
• 양방향 연결 리스트는 각 노드가 앞뒤 양방향으로 링크된다.

Code

Github