메모리상에서 연속적으로 저장되어 있는 특징을 갖기때문에, index를 통한 접근이 용이하다.
배열의 크기는 처음 생성할 때 정하며 이후에는 변경할 수 없다.
시간복잡도
탐색: O(1) 단, 접근하고자 하는 인덱스를 알고있어야 한다. 순차적으로 탐색시에는 O(n)
삽입 및 삭제:
배열의 처음 또는 중간에 삽입 및 삭제: O(n) 삽입 지점 이후의 데이터를 옮겨야 하기 때문이다.
배열의 끝에 삽입 및 삭제: O(1)
연결리스트
연결리스트는 여러 개의 노드들이 순차적으로 연결된 형태를 갖는 자료구조이며, 첫번째 노드를 헤드(Head), 마지막 노드를 테일(Tail) 이라고 한다.
각 노드는 데이터와 다음 노드를 가리키는 포인터로 이루어져있다.
배열과는 다르게 메모리를 연속적으로 사용하지 않는다.
배열과는 다르게 순차적으로 접근해야 하는 면에서 불리할 수도 있으나, 노드가 연결된 구조이기 때문에 삽입, 삭제에 용이하다.
시간복잡도
탐색: O(n)
삽입 및 삭제: 삽입과 삭제 자체는 O(1) 이다.
연결리스트의 처음에 삽입 및 삭제: O(1)
연결리스트의 중간에 삽입 및 삭제: O(n) 탐색시간 소요
연결리스트의 끝에 삽입 및 삭제:
끝을 가리키는 별도의 포인터를 갖는 경우: O(1)
끝을 가리키는 별도의 포인터를 갖지 않는 경우: O(n) 탐색시간 소요
연결리스트 연산
삽입
노드를 생성하고, 삽입하려는 위치를 찾는다.
삽입할 노드를 NewNode라고 하면, NewNode가 그 다음 노드를 가리키게 한다.
NewNode.next -> RightNode
새로 삽입한 노드의 이전 노드가 새로운 노드를 가리키게 한다.
LeftNode.next -> NewNode
삭제
탐색을 통해 삭제하고자 하는 노드 (TargetNode)를 찾는다.
TargetNode의 왼쪽 노드가 TargetNode의 오른쪽 노드를 가리키게 한다. LeftNode.next -> TargetNode.nextTargetNode가 RightNode를 가리키지 않게 한다TargetNode.next -> NULL
배열과 연결리스트 비교
배열
연결리스트
장점
인덱스를 통한 빠른 접근이 가능하다.
삽입과 삭제가 용이하다.
단점
삽입과 삭제가 오래 걸린다. 배열 중간에 있는 데이터가 삭제되면, 공간 낭비가 발생한다.
임의 접근이 불가능하여, 처음부터 탐색을 진행해야 한다.
용도
빠른 접근이 요구되고, 데이터의 삽입과 삭제가 적을 때
삽입과 삭제 연산이 잦고, 검색 빈도가 적을 때
이중 연결리스트와 원형 연결리스트
이중 연결리스트
이중 연결리스트는 위에서 언급한 연결리스트(단순 연결리스트)와 다르게 전, 후로 탐색이 가능한 구조이다.
즉, 단순 연결리스트의 노드는 데이터와 다음 노드의 주소를 저장한다면, 이중 연결리스트의 노드는 데이터, 이전 노드의 주소와 다음 노드의 주소를 저장하게 된다.
장점
단순 연결리스트에서는 최악의 경우 n번의 탐색을 해야하지만, 이중 연결리스트에서는 얻고자 하는 데이터의 위치가 tail에 가깝다면 tail에서 부터 역방향으로 탐색이 가능하기 때문에 탐색 시간을 줄일 수 있다.
원형 연결리스트
원형 연결리스트는 단순 연결리스트의 마지막 노드가 null을 가리키는게 아닌, 처음 노드를 가리키는 구조이다.
즉, head에서부터 순회를 반복적으로 진행하다보면 다시 처음으로 돌아오는 구조이다.
이중 연결리스트도 마지막 노드가 처음 노드를 가리키는 구조가 되면, 이를 이중 원형 연결리스트라고 한다.
