Array와 List
- Data structure
- 2021년 6월 3일
1. 배열
가장 기본적인 자료구조로써, 논리적 저장 순서와 물리적 저장 순서가 일치하고 인덱스를 통하여 원소에 접근이 가능하다.
대부분의 언어에서 [] 를 이용해서 배열을 제공한다.
2. 리스트
배열과 달리 원소들 간의 논리적인 순서로 연결되어 구성있고, 삽입과 삭제를 수행하기 위해서는 첫 원소부터 모두 search해야한다.
자료구조 Tree에 기본이 되는 자료구조이다.
1) 단순 연결 리스트
방향이 한쪽으로만 구성된 리스트이다.
구현 방법
한개의 노드에는 key값과 다음 노드의 주소를 가르킬 포인터 변수로 구성되어 새로 삽입할때 노드를 새로생성해서 리스트의 끝노드의 포인터로 새로운 노드를 가리키면 된다.
시간 복잡도
노드의 개수가 n개일 경우 탐색/삽입/삭제 모두 O(n)만큼 걸린다.
2) 이중 연결 리스트
리스트 방향이 양쪽으로 구성된 리스트이다.
구현방법
- 한개의 노드에는 key값과 이전 노드와 다음 노드의 주소를 가르킬 포인터 변수 2개로 구성
- 첫 노드 생성시 left/right node pointer는 null로 초기화
- 노드 생성시 leftNode는 왼쪽 노드를 rightnode는 null로 생성후 원래 있던 끝 자락 노드의 right node*를 생성한 노드에 연결