배열(Array)

  • 인덱스를 통해 Value에 접근함.

  • 배열 가운데의 원소가 삭제되면 null 값이 들어감. (밀도≠1)

  • 인덱스를 통한 검색시 : O(1)

연속 리스트(ArrayList) = 선형 리스트, 순서 리스트

  • 배열과 같이 인덱스를 통해 Value에 접근함.
  • 배열 가운데 원소가 삭제되면 null값이 들어가지 않고 뒤의 원소가 앞으로 땡겨져 채워넣음 (밀도=1)
    -> 삽입, 삭제시 원소의 이동이 일어나기 때문에 번거롭다.

  • 연속적으로 놓여있어 검색은 용이하지만 삽입, 삭제시 용이하지 않음.

  • 인덱스를 통한 검색시 : O(1)
  • 삽입, 삭제시 : O(n)

연결 리스트(LinkedList)

  • 노드 + 포인터
  • 자료들을 연속적으로 배열시키지 않고 임의의 기억공간에 기억시키되, 자료 항목의 순서에 따라 노드의 포인터 부분을 이용하여 자료를 연결시킴.
  • 포인터 부분이 필요하기 때문에 기억공간 효율이 좋지 못함.
  • 원소의 이동이 필요 없기 때문에 삽입, 삭제시 용이하나 검색시 포인터를 통하기 때문에 접근속도가 느림

  • 헤드포인터가 첫번째 노드의 주소를 갖고 있고, 마지막 노드는 포인터에 NULL을 저장 (원형 연결 리스트의 경우 마지막 노드에 첫번째 노드의 주소를 갖음.)

  • 검색시 : O(n)
  • 삽입, 삭제시 : O(1)

(1) 단순 연결 리스트 : 1개의 포인터만 갖고 있으로 다음 노드를 가르킴
(2) 이중 연결 리스트 : 2개의 포인터를 갖고 있어 앞&뒤 노드를 가르킴
(3) 원형 연결 리스트 : 마지막 노드의 포인터가 첫번째 노드를 가르킴