순서 리스트

최종 수정 : 24.12.26

순서 리스트

1. 정의

리스트는 자료를 나열한 목록 또는 자료의 집합이며, 순서 리스트는 자료 간에 순서를 갖는 리스트를 의미한다.

 

1) 순서 리스트(dense list, linear list, sequence list)

기억공간에 연속적으로 저장된 자료의 구조로, 대표적으로 배열과 같다.

 

장점

• 저장구조가 단순하다.
• 기억공간에 연속으로 저장되므로 기억효율이 좋다.
• 순차 접근에 빠른 속도를 제공한다.

 

단점

• 삽입, 삭제, 갱신의 작업에서 전체를 복사해야 하므로 작업속도가 느리다.
• 특정 자료에 접근할 때 처음부터 순서대로 접근하면서 찾아야 하므로 접근 시간이 O(n) 시간이 걸리고, 자료가 많을수록 검색속도는 떨어진다.

 

2) 연결 리스트(linked list)

기억공간에 불연속적으로 저장된 구조로, 링크라고 불리는 주소(포인터)에 의해 각 데이터(노드)들이 연결되는 구조를 갖는다.

 

장점

• 데이터의 삽입/삭제가 쉬워, 잦은 데이터 갱신이 발생할 때 유리하다.
• 리스트의 분리와 결합이 쉽다.

 

단점

• 링크를 따라 접근해야 하므로 검색 속도가 느리다.
• 링크를 위한 추가 기억공간이 필요하므로 기억효율이 떨어진다.
• 중간의 노드가 손실되면 이후 노드를 찾기 어렵다.

---

2. 순서 리스트의 표현과 연산

1) 순서 리스트 표현

집합 또는 배열로 표기할 수 있으며, 원소를 {} 내에 나열한다. 일반적인 형식은 "리스트이름 = (원소1, 원소2, ...)"와 같이 리스트의 이름과 리스트의 순서대로 데이터를 나열한다.

 

2) 순서 리스트 연산

원소의 삽입과 삭제는 수행 후 리스트 전체를 정리하는 작업이 필요하다. 이는 리스트 전체를 새로 복사하는 것과 같기 때문에 삽입과 삭제 연산의 효율이 떨어진다.

 

3) 검색 연산

시간 복잡도를 표기하면 O(n)이 되므로 데이터의 개수가 많아지면 효율이 낮아진다.

---

참고

독학사 교재