티스토리 뷰

컴퓨터 메모리에 뭔가를 저장해야 할 때

  1. 컴퓨터에게 저장 공간을 요청한다.
  2. 컴퓨터는 뭔가를 저장할 수 있는 주소를 알려준다.

이 때 여러 개의 원소를 저장해야 한다면 여러 개의 주소가 필요할 텐데, 선형적으로 저장한다고 가정하면 배열이나 리스트 중 하나로 저장하게 된다. (선형적이지 않은 저장 방법으로는 트리나 그래프 등이 있다)

 

배열(Array)

만약 10개의 원소를 배열로 저장해야 한다면, 메모리에 연달아 있는 10개 공간을 할당한다.

배열의 장점

인덱스가 주어지므로 빠르게 접근할 수 있다.

배열의 단점

처음에 3개의 공간만 요청했다가 공간이 1개 더 필요하게 되면, 이 때 공간 4개를 재요청해야 한다. 즉 사전에 할당한 공간 내에서만 저장이 가능하고 이 공간 범위를 벗어날 경우 재요청이 필요하다.

이를 해결하기 위해서 애초에 공간을 넉넉하게 요청할 수도 있는데, 만약 추가할 일이 생기지 않으면 메모리 낭비가 생기는 셈이고 추가하더라도 그 넉넉한 범위를 벗어날 가능성은 언제나 있다.

또한 삽입과 삭제가 느리다. 원소 한 개를 삽입하더라도, 그 삽입 위치 뒤의 원소들은 모두 하나씩 이동해야 한다. 삭제 또한 마찬가지이다.

 

연결 리스트(Linked List)

여러가지 메모리 주소들이 하나의 목록으로 연결되어 있다. 첫 번째 주소로 가면 두 번째 주소에 대한 정보가 있고, 두 번째 주소로 가면 세 번째 주소에 대한 정보가 있는 식이다. 그러므로 배열처럼 연달아 메모리를 할당하지 않고, 빈 곳 아무데나 저장한 다음 그 주소를 바로 앞의 원소에 저장해놓기만 하면 된다.

리스트의 장점

삽입과 삭제가 빠르다. 리스트는 이전 원소가 무엇을 가리키는지 바꾸기만 하면 된다.

리스트의 단점

읽기가 느리다. 배열과 달리 순차 접근(sequential access)을 하여 첫 번째 원소부터 읽어야 하기 때문에 n번째 원소를 읽으려면 연산이 n번 필요하다.

 

빅오 표기법으로 나타내기

  • 배열

    • 읽기: O(1)
    • 삽입: O(n)
    • 삭제: O(n)
  • 링크드 리스트

    • 읽기: O(n)
    • 삽입: O(1)
    • 삭제: O(1)

단 삽입과 삭제는 가장 마지막 원소 또는 가장 첫 번째 원소를 가정한 것이다. 즉 바로 접근이 가능할 때에만 링크드 리스트에서 삽입과 삭제가 O(1)이 걸린다는 소리이다.

 

'Data Structure & Algorithm' 카테고리의 다른 글

선택 정렬(Selection Sort)  (0) 2019.11.30
버블 정렬(Bubble Sort)  (0) 2019.11.30
[파이썬] 야근지수 문제  (1) 2019.09.23
[JS] 가장 먼 노드(그래프 탐색)  (0) 2019.07.02
[Java] LinkedList  (0) 2019.05.31
댓글
공지사항
최근에 올라온 글
최근에 달린 댓글
Total
Today
Yesterday
링크
«   2024/03   »
1 2
3 4 5 6 7 8 9
10 11 12 13 14 15 16
17 18 19 20 21 22 23
24 25 26 27 28 29 30
31
글 보관함