[ 알고리즘 ] 배열과 링크드 리스트

배열 ( Array )

배열은 연속된 메모리 공간에 같은 타입의 데이터를 할당하는 선형 자료 구조이다.

배열의 크기는 선언 시점에서 정해야하며 int Five_grade[30] = {1,2,3,4,5 ..} 배열 생성 시, 선언한 크기만큼의 메모리가 할당된다.

예를 들자면 학교의 출석부 같은 구조라고 할 수 있다.

처음 반을 등록할 때 출석부라는 이름의 메모리에 30번 까지 준비(할당)하고 들어오는 학생(데이터) 들을 순차적으로 넣는 방식이다.

검색 성능이 좋다. 시간 복잡도 O(1)
- 자신의 할당된 인덱스(번호)로 액세스 ( 번호 부르기 ) 가 가능하다.
- ex) 오늘 12일이니까, 12번이 나와서 읽어봐
순차 접근의 경우에도 데이터가 하나의 공간에 할당되어서, 연결 리스트보다 빠르다.
- 출석부가 한눈에 보이기 때문에, 연결 리스트 방식보다 더 빠르게 찾기 가능
- ex) 출석 부를때 순차적으로 접근한다.

자료의 삽입과 삭제가 비효율적이다. 시간 복잡도 O(n)
- 출석부에 새로운 학생이 들어오거나, 학생이 전학가면 기존의 출석부를 걔 번호 뒤에 애들을 전부 뜯어 고쳐야한다.
배열 크기에 대한 변경이 불가능하다.
- 반 인원 제한이 30명이라서 새로운 학생이 30명 보다 많이 전학오면 더 받을 수 없는 상황이 발생한다.
메모리의 재사용이 불가능하다.
- 처음에 출석부 크기를 지정했기 때문에 학생들이 5명만 남아도, 나머지 25명의 자리 만큼의 공간이 낭비되지만, 처음 크기를 정했기 때문에 낭비가 발생한다.

연결 리스트는 비연속적으로 할당된 데이터들을 주소 값으로 연결해놓은 리스트이다.

첫 번째 정보를 담은 노드는 Head 노드, 마지막 노드는 Tail 노드라고 한다.

각 노드에는 데이터를 담은 Value 와, 다음 노드를 가리키는 포인터로 구성된다.

아까와 같이 학교의 예를 들자면 이번에는 출석부를 만드는게 아니라, 1번 학생을 정해놓고 이 학생에게 다음 학생의 이름이 적한 출석부를 주는 것이다.

데이터의 삽입과 삭제가 간단하다. 시간 복잡도 O(1)
- 이 반에 새로운 학생인 경훈이가 전학 온다면( 새 데이터 삽입 ), 바로 전 학생인 희철이가 갖고 있던 다음 번호의 정보를 경훈이에게 주고, 희철이에게 다음 번호인 경훈이의 번호를 주면 된다.
크기가 가변적이다. ( 새로운 원소 추가 시 동적으로 크기가 변함 )
- 저번 학교는 출석부 크기가 정해져 있어서, 이 크기 이상의 학생을 받지 못했지만 이 학교에서는 학생들에게 계속 다음 번호가 쓰인 정보를 주기만 하면 몇명이라도 받을 수 있다.
불연속 메모리 할당.
- 출석부를 고정적인 칸을 만들지 않았기 때문에 출석부에 남는 부분이 없다.

인덱스 접근이 느리다. 시간 복잡도 O(n)
- 11번째 학생이 궁금하다면, 1번 학생에게 가서 다음 학생이 쓰여진 종이를 보고, 다음 번호 학생에게 가서 그 다음 번호를 보는 것을 반복해야한다. 인덱스(출석번호) 가 지정되어 있지 않아서 11번을 불러도 의미가 없다.
포인터로 인한 저장 공간의 낭비.
- 학생들이 다음 번호 학생의 정보를 꼭 가지고 있어야하기 때문에, 학생들 입장에선 배열 학교에선 굳이 없어도 되는 공간이 낭비되는 셈이다.

시작 부분에 Head 가 있으며, 다음 값을 가리키는 주소 값을 가지고 있음.

단방향으로만 진행되는 리스트이다. 마지막 부분의 List 는 null 값을 가지고 있다.

양방향으로 이동 가능한 리스트로, 노드에서 다음 노드를 가리키는 주소값과 이전 노드를 가리키는 주소 값 두 개를 다 가지고 있음. 첫 번째 노드의 Prev 와 마지막 노트의 Next 는 null 값 을 가리킴

원래 단방향보다 더 많은 메모리를 써야함.

단순 연결 리스트와 같지만, 마지막 노드가 첫번째 노드를 가리킴.

마지막이 첫번째 노드를 가리킴으로, 마지막 노드인 Tail 의 정보만 있으면 Tail 의 next 가 head 이기 때문에 Head 가 없고 대신 Tail 변수가 생김

Reference