[Python] 자료구조 - 리스트

 

 

리스트

 

 

리스트는 스택, 큐와는 달리 자료에 대한 접근에 제한이 없습니다.

즉, 어느 위치에서든 요소를 삽입하고 삭제할 수 있습니다.

요소의 중복도 허용되고, 순서도 있어서 인덱싱으로 자료 접근도 쉬워서

자료 구조 중에서 가장 활용이 자유롭고 많이 사용됩니다.

 

 

리스트는 크게 배열 구조와 연결된 구조를 가집니다.

 

 

---

 

 

배열 구조

 

 

배열 구조의 리스트

 

배열 구조는 우리가 잘 아는 일반적인 구조로

빈자리가 없이 반드시 메모리의 연속된 공간에 저장됩니다.

 

용량이 고정되어 있어

용량을 줄이거나 늘리기 힘들어서

메모리 낭비가 되거나 포화상태가 되기 쉽습니다.

 

요소를 삽입할 때는

삽입한 요소의 뒤의 요소들을 모두 한 칸씩 밀어야 하고,

 

요소를 삭제할 때는

삭제하고 생긴 빈 공간을 채우기 위해서

삭제한 요소의 뒤의 요소들을 모두 한 칸씩 당겨야 합니다.

 

2를 삭제하고서 3, 4를 이동시키기

 

 

비효율적입니다..

 

 

파이썬의 리스트

 

 

파이썬의 리스트

 

배열 구조의 리스트는 파이썬에서 기본적으로 제공해주는데

위에서 설명해준 배열 구조에서 업그레이드된 동적 배열 구조를 가집니다.

 

동적 배열 구조의 리스트는

리스트가 가득 찼을 때 리스트의 크기를 자동으로 늘려주고

 

요소가 추가될 때마다

크기를 동적으로 조절하기 때문에

메모리를 효율적으로 사용할 수 있습니다.

 

 

---

 

 

연결된 구조

연결된 구조의 리스트

 

연결된 구조는 데이터가 연속된 공간에 저장되어 있지 않고

메모리 이곳저곳에 흩어져 저장되어 있습니다.

 

데이터가 흩어져 있기 때문에

링크를 통해 다음 데이터의 위치를 가리켜줘야합니다.

 

데이터를 가지고 있는 곳을 노드라고 하는데요,

 

따라서 연결된 구조의 리스트의 노드에는

데이터 외에 링크를 추가적으로 갖고 있습니다.

 

특징으로는

 

데이터의 크기에 맞게

융통성 있게 용량을 설정하기 때문에

메모리를 효율적으로 사용할 수 있습니다.

 

노드를 삽입하거나 삭제할 때는

해당 노드의 바로 직전의 노드의 링크만 수정하면 되기 때문에

매우 효율적입니다.

 

다만 연결된 구조 리스트의 노드에 접근을 할 때

머리노드에서부터 여러 링크를 타고 가서 찾아야하는

번거로움이 있습니다..

 

연결된 구조의 리스트의 종류로는

단순 연결 리스트, 원형 연결 리스트 그리고 이중 연결 리스트가 있습니다.

 

 

단순 연결 리스트

 

 

단순 연결 리스트

 

단순 연결 리스트는 하나의 방향으로만 연결된 리스트입니다.

링크에 다음 노드의 주소를 저장하여 링크를 통해 다음 노드로 이동할 수 있습니다.

 

리스트의 마지막 노드인 꼬리 노드 다음에는 어떤 노드도 없으므로

꼬리 노드의 링크에는 None이 저장됩니다.

 

노드의 삭제와 삽입 모두 링크를 수정하여

쉽게 구현해줄 수 있습니다.

 

 

자세한 코드는 아래 pdf에 작성해놓았습니다.

 

 

이중 연결 리스트

이중 연결 리스트

 

이중 연결 리스트는 이전 노드와 다음 노드를 가리키는 링크가 있는 리스트입니다.

따라서 하나의 링크만 가진 단순 연결 리스트보다 하나의 링크를 더 가집니다.

 

머리 노드는 이전 노드가 없으므로

이전 노드를 가리키는 링크는 None을 저장하고,

 

꼬리 노드의 다음 노드가 없으므로

다음 노드를 가리키는 링크도 None을 저장합니다.

 

 

자세한 코드는 아래 pdf에 작성해놓았습니다.

 

 

리스트.pdf

0.38MB