서문
자료구조 배열과 연결리스트에 대하여 공부한 내용을 정리했습니다.
1. 배열(Array)
우리에게 친숙한 이름 배열(Array) 자료구조에서는 어떨까?
배열은 입력된 데이터들이 메모리 공간에서 연속적으로 저장되어 있는 정적(static)인 자료구조이다.
왜 정적인가에 대하여 설명하자면,
배열을 만들기 위해서는 미리 배열의 크기를 정해놓고,
크기가 정해진 배열들은 그 크기만큼 연속된 메모리 주소를 할당 받는다.
따라서 한번 크기를 정해두면 수정이 불가능하고, 해당 크기 이상의 데이터를 저장할 수 없다는 단점이 존재한다.
하지만 연속된 메모리 주소를 할당받기에 데이터가 인덱스를 가지게 되면서 임의 접근(random access)이 가능해진다.
배열의 데이터 탐색, 추가, 삭제는 다음과 같다.
탐색 시,
임의 접근 방식을 사용하기 때문에 인덱스 번호를 통해 빠르게 탐색 가능하며 O(1)의 시간 복잡도를 가진다.
삽입 시,
추가하려는 데이터가 맨 뒤가 아니라면, 기존 데이터들의 위치를 한 칸씩 이동시켜야하므로
O(n)의 시간 복잡도를 가지게 된다.
추가하려는 데이터의 위치가 맨 뒤이고 배열에 공간이 남아있다면 O(1)의 시간 복잡도를 가지게 된다.
삭제 시,
삭제하려는 데이터의 위치가 맨 뒤가 아니라면, O(n)의 시간 복잡도를 가지게 된다.
삭제하려는 데이터의 위치가 맨 뒤이고 배열에 공간이 남아있다면, O(1)의 시간 복잡도를 가지게 된다.
따라서 데이터 삽입 & 수정 시 맨 뒤가 아니고 배열에 공간이 남아 있지 않다면 비효율적이다.
2. 연결리스트(Linked List)
연결리스트는 여러 개의 노드들이 순차적으로 연결된 형태를 갖는 동적(dynamic)인 자료구조이며,
각각의 데이터가 메모리 공간 상에 고유한 노드로 존재한다.
그리고 이러한 노드들의 첫번째 노드를 헤드(Head), 마지막 노드를 테일(Tail)이라고 한다.
이때문에 기차로 든 예시가 많다.
연결리스트가 정적이 아닌 동적인 이유로는 배열과 달리 크기를 미리 정할 필요가 없기 때문이다.
연결리스트는 미리 연속된 메모리 주소를 할당받는 것이 아니기에
각 노드에 저장된 데이터 값과 자신의 앞에 있는 데이터와 뒤에 있는 데이터에 대한 주소를 가지고 있다.
이러한 특징으로 인해 크기의 제한이 걸리지 않고, 데이터의 추가 삭제가 자유롭다.
하지만 배열과 달리 연속적으로 메모리 주소를 할당받지 않기 때문에 임의 접근(random access)이 불가능하며 순차 접근(sequential access) 방식을 사용한다.
연결리스트의 탐색, 추가, 삭제는 다음과 같다.
탐색 시,
순차 접근 방식을 사용하기 때문에 O(n)의 시간 복잡도를 가진다.
삽입 시,
추가하려는 데이터의 위치가 맨 앞이라면 O(1)의 시간 복잡도를 가진다.
추가하려는 데이터의 위치가 맨 앞 그 이후라면 O(n)의 시간 복잡도를 가진다.
삭제 시,
삭제하려는 데이터의 위치가 맨 앞이라면 O(1)의 시간 복잡도를 가진다.
삭제하려는 데이터의 위치가 맨 앞 그 이후라면 O(n)의 시간 복잡도를 가진다.
정리
연결 리스트는 노드가 있기에 데이터 추가, 삭제로부터 자유롭지만 탐색이 느려진다.
배열은 연속적으로 메모리를 할당 받아 데이터를 저장하기에 탐색은 빠르지만 추가 삭제로부터 자유롭지 못하다.
따라서
데이터의 접근, 탐색이 중요하다면 배열을,
추가 삭제가 중요하다면 연결리스트를 선택하여 사용 할 수 있다.
