학습 동기

평소에 목록을 저장하기 위해서 배열이나 List 자료 형을 썼었는데, 배열과 ArrayList 는 메모리 크기가 고정되어 있는지, 동적으로 커지는지에 차이가 있다고 생각되어 구분하여 잘 사용 했었습니다. 그런데 알고리즘을 풀면서 LinkedList 와는 잘 비교해서 사용하지 않았던 것 같아서 정리해보고자 합니다.

배열(Arrays)

  • 배열은 입력된 데이터들이 메모리 공간에서 연속적으로 저장되어 있는 자료구조에요
  • Index 를 통해서 접근이 가능하고 0 번부터 시작합니다.
  • 최초 크기가 고정되면 바꿀 수 없어요.

시간 복잡도

  • 조회는 접근하고자 하는 인덱스만 안다면 O(1) 시간이 걸려요.
    • 순차 탐색시는 최대 O(n) 이 소모됩니다.
  • 삽입 및 삭제

    • 배열의 처음 또는 중간 삽입, 삭제 O(n)

      삭제된 원소 뒤에 있는 원소들을 한칸씩 옮겨야 해서 O(n) 이 소모됩니다.

    • 배열의 끝에 삽입 및 삽입, 삭제 O(1)

      가장 뒤에는 옮길 원소가 없기 때문에 O(1) 이 소모됩니다.

사용하면 좋은 상황

ArraysList 같은 경우는 메모리가 초과됐을 경우 특정 크기를 1.5배씩 증가 시키기 때문에 메모리 낭비가 있을 수 있어서 전체 원소의 메모리 사이즈를 알고 있다면 배열을 사용하는게 좋을 것 같아요.

LinkedList

연결 리스트는 여러개의 노드가 순차적으로 연결된 형태를 가지는 자료구조이며, 첫번째 노드를 HEAD , 마지막 노드를 TAIL 이라고 합니다.

원형 LinkedList Node 구조

  • data 와 Next node 주소값을 가져요.
class Node {
		Object data;
		Node<E> next;
}

특징

  • 배열과 다르게 메모리를 연속적으로 사용하지 않아요!
  • index 로 접근할 수 없기 때문에 순차 접근에는 분리할 수 있으나 노드가 연결된 구조이기 때문에 중간 삽입, 삭제시, 앞 뒤 노드만 연결해주면 되기 때문에 훨씬 효율적이에요!

시간 복잡도

  • 조회에는 O(n) 시간이 소모됩니다.
  • 맨 앞 삽입,삭제 자체는 O(1) 이지만 중간 삽입,삭제는 탐색 시간이 소요되어 O(n) 이 걸려요.
    • 연결리스트 맨 끝에 삽입할 때 만약 마지막 노드의 위치를 알고 있다면 O(1) 시간만으로도 해결할 수 있어요.

삽입 flow

  • 노드를 생성하고, 삽입하려는 위치를 찾아요
  • 위치를 찾았으면, 삽입하려는 노드가 그 위치에 다음 노드를 가리키게 합니다.
  • 삽입하려는 위치에 이전 노드는 삽입 노드를 가리키게 합니다.

삭제 flow

  • 탐색을 통해서 삭제하려는 노드를 찾습니다.
  • 삭제하려는 노드의 왼쪽 노드를 삭제하려는 노드의 오른쪽을 가리키게 합니다.
  • 삭제하려는 노드의 nextNode 를 null로 만들어줍니다.

사용하면 좋을 상황

삽입과 삭제에서 배열보다 유리하기 때문에 삽입 삭제가 빈번히 발생하고 검색이 적을 때 사용하면 좋을 것 같습니다. 그 중에서도 삽입 삭제가 맨 앞에서 일어나는 상황이라면 더 LinkedList의 장점을 극대화해서 사용할 수 있겠습니다 ㅎㅎ

이중 LinkedList Node 구조

  • prev Node 주소값과 data, Next node 주소값을 가져요.
class Node {
		E item;
    Node<E> next;
    Node<E> prev;
}

특징

  • 위에서 언급한 단순 연결리스트와는 다르게 전, 후로 탐색이 가능한 구조입니다. 이전 노드주소와 이후 노드 주소를 한 노드에서 모두 알고 있습니다!
  • 가장 마지막 노드를 기억하고 있는 tail ! 만약 탐색하고 싶은 노드가 가장 뒤에서 부터라면 뒤에서 앞으로 탐색할 수 있어서 탐색 시간을 줄일 수 있어요.

느낀점

자료구조 내부에 동작원리를 알게 되므로 코드를 작성할 때 타입 선택을 할때 메모리가 고정되어 있다면 배열을 사용하고, 동적이라면 ArrayList, 검색은 별로 안하지만 삽입 삭제가 많으면 LinkedList 를 사용해야겠다는 것을 알게 되었어요. 자료형을 선택할 때는 항상 이유있는 선택을 해야겠어요.

참고자료