List

리스트 자료구조

• 리스트는 데이터를 순서대로 나열한(줄지어 늘어놓은) 자료구조 입니다. 이때 중복된 데이터를 허용합니다.

배열기반 선형리스트

• 같은 타입의 데이터를 연속된 메모리 공간에 저장하는 배열도 선형리스트로 구현이 가능하다.
• 장점
  • 데이터 검색, 이동시에는 인덱스 값으로 접근이 가능하므로 -> '상수'시간 만큼 소요됨
• 단점
  • 데이터의 삽입, 삭제에 따라 리스트에 정의에 따라 삽입, 삭제에 따라 데이터를 모두 옮겨야 하기 때문에 효율이 좋지 않습니다.
  • 배열은 선언 이후에는 크기를 변경할 수 없기 때문에 최초 선언시 쌓이는 데이터의 크기를 알아야한다.

구조체와 포인터로 연결기반 선형리스트

• 배열 기반 선형리스트의 단점을 극복하기 위해 다음 노드를 가리키는 포인터를 각 노드에 포함시키는 연결리스트
• 장점
  • 데이터의 삽입의 경우 삽입하는 데이터의 위치를 앞뒤 노드에 연결시키면 되므로 나머지 데이터를 이동시켜야 할 필요가 없다.
  • 데이터의 삭제의 경우 삭제되는 데이터 다음 노드의 위치를 삭제되는 데이터 앞노드에 연결시키면 데이터를 이동시켜야 할 필요가 없다.
• 단점
  • 데이터 검색시 머리 데이터로부터 이동하면서 검색해야하므로 많은 시간이 소요 됨