array-list

배열

가장 기본적인 자료구조로써, 논리적 저장 순서와 물리적 저장 순서가 일치.
인덱스를 통하여 원소에 접근이 가능하다.
원소를 삭제하게 될 경우 연속적 특징이 깨지기 때문에 옮겨주는 비용이 추가로 발생하게 된다.
삽입의 경우도 삽입 위치 이후의 원소들을 옮겨주어야하기 때문에 비용이 추가로 발생.

리스트

배열과 달리 원소들 간의 논리적인 순서로 연결되어 구성
삽입과 삭제를 수행하기 위해서는 첫 원소부터 모두 search해야한다.
자료구조 Tree에 기본이 되는 자료구조

✔ 단순 연결 리스트

• 리스트의 방향이 한쪽으로만 구성

• 구현 방법

  • 한개의 노드에는 key값과 다음 노드의 주소를 가르킬 포인터 변수로 구성

• 시간 복잡도

  • 노드의 개수가 n개일 경우 O(n)

c언어를 이용한 코드 예

✔ 이중 연결 리스트

• 리스트 방향이 양쪽으로 구성

• 구현방법

  • 한개의 노드에는 key값과 이전 노드와 다음 노드의 주소를 가르킬 포인터 변수 2개로 구성

  • 첫 노드 생성시 left/right node pointer는 null로 초기화

  • 노드 생성시 leftNode는 왼쪽 노드를 rightnode는 null로 생성후 원래 있던 끝 자락 노드의 right node*를 생성한 노드에 연결

c언어를 이용한 코드 예