자바의 자료구조 - 연결리스트

  : 연결리스트는 순차적으로 연결된 자료구조이다.

     A, B, C가 있다면

     A는 B의 위치를 기억하고, B는 C의 위치를 기억하는 구조이다.

     A만 알고있으면, 순서대로 나아가기만 하면 전체를 알 수 있다.

     다만 이 방식으로만 다른 원소들에 접근할 수 있고, B나 C에 바로 접근할 수는 없다.

 

 : 연결리스트 성질

     1. k번째 원소를 확인 / 변경하기위해 O(k)가 필요
     2. 임의의 위치에 원소를 추가 / 임의의 위치의 원소를 제거 O(1)
     3. 원소들이 메모리상에 연속해 있지 않아 Cache hit rate가 낮지만
        할당이 다소 쉬움

 

     연결리스트에서는 임의의 위치에 원소를 추가하거나 임의 위치 원소 제거가 O(1)이다.
     배열과 비교시 가장 큰 차이가 있는 성질이고, 연결 리스트의 장점이다.

     이는 밑에서 좀 더 자세히 다뤄보자.

     데이터가 메모리상에 연속해 있지 않기때문에 
     Cache hir rate가 낮지만 할당이 쉽다. 이 부분은 알고리즘의 영역이 아니기에 생략한다.

 

 : 연결리스트의 종류

     단일 연결 리스트,
          단일 연결 리스트는 각 원소가 자신의 다음 원소의 주소를 들고 있는 연결리스트이다.

     이중 연결 리스트,
          이중 연결 리스트는 각 원소가 자신의 이전, 다음 원소의 주소를 갖고 있다.
          단일 연결리스트는 주어진 원소의 이전 원소가 무엇인지를 알 수 없지만
          이는 알수 있게 된다. 다만 원소에 포함시키는 정보가 1개 추가되니 메모리를 더 사용하게 된다.
          STL에 연결리스트가 있는데 이 컨테이너의 이름은 list이고 구조는 이중 연결 리스트이다.( C언어 )
     
     원형 연결 리스트,
          원형 연결 리스트에는 끝과 처음이 연결돼있다.
          각 원소는 단일 연결리스트여도 되고 이중 연결 리스트여도 된다.

 

( 출처 : https://blog.encrypted.gg/932 )

 

     배열과 연결리스트는 데이터가 일렬로 늘어선 것과 같은 자료구조이다. ( 연결리스트는 주소는 연속적이지 않다. )

     이러한 자료구조는 선형 자료구조라 한다. 

 

     k번째 원소의 접근은 배열은 O(1), 연결리스트는 O(k)이다.
     이건 순차적으로 찾아가는 것과 index를 바로 접근하는것으로 알 수 있다.

     임의 위치에 원소를 추가/제거하는 건 배열은 O(n), 연결리스트는 O(1)이다.
     연결리스트는 n번째 원소 뒤에 x라는 원소를 추가하려면 
     n번째 원소 접근 후에 O(1)추가가 가능하기에 조금 자세하게 볼 필요가 있겠다.

     메모리 상의 배치는 배열은 연속이고, 연결 리스트는 불연속이다. 
     필요한 공간 ( overhead )을 생각해보면
     배열은 데이터만 저장하면 된다. ( 길이 정보를 저장할 int 1개 추가되지만 미미함 )
     연결리스트는 각 원소와 다음, 혹은 이전과 다음 원소의 주소값을 저장해야 한다.
     32비트 컴퓨터의 경우 주소값이 32비트 ( = 4바이트 ), 
     64비트 컴퓨터라면 주소값이 64비트 ( = 8바이트 ) 단위이니 8n 바이트가 추가로 필요하다. 
     즉 n에 비례하는 만큼의 공간 복잡도가 증가한다.

 

 : 접근, 추가, 삭제에 대한 시간복잡도의 과정

     임의의 원소를 확인/수정하기 위해 k번째 원소를 확인한다면 
     1번째 원소를 통해 2번째 원소의 주소를 받고,
     2번째 원소를 통해 3번째 원소의 주소를 받고,
     ,
     ,
     ,
     k번째 원소에 접근
     하게 된다. 그럼 n개의 원소가 있는 경우 평균적으로 O(n/2)의 시간복잡도를 갖게되고
     결과적으로 O(n)의 시간복잡도를 갖게된다. ( n에 따라 상수는 비중이 낮아진다. )


     임의의 위치에 원소를 추가하는 연산은 O(1)에 가능하다.
     이유로 A뒤에 B를 추가할때,
     A와 B에서 다음 원소의 주소만 변경을 하게되면 되기 때문이다.

     당연히 이건 단편적으로 '추가'하는 과정의 시간복잡도이고,
     실제로 A의 주소를 알지못해 A에 접근하여야 하는 과정이 필요하다면 시간복잡도는 증가하게 된다.
     ( 사실 이걸 분리해서 이야기할 줄은 몰랐다. 그래도 로직을 짜다보면 주소를 알게 된 후에 
       연산을 요하는 과정이 있을 수 있어 그런가보다. )


     임의의 원소를 제거하는 연산은 O(1)에 가능하다. 이 역시 추가와 동일하게 보면 될 것같다.
     다만 처리되는 과정은 약간 상이한데,
     A B C가 순차적으로 있을때, A가 B가 아닌 C를 가르키게 하면 된다.
     B는 메모리 누수를 막기위해 삭제하면 된다. 
     ( C기준, 자바는 가비지컬렉션이 하지않을까 싶음. )
     ( 가비지 컬렉션은 추후 다뤄볼 예정 )

 : 구현
     내 깃허브에도 진행해보았지만, 잘 설명되어있는 코드가 있어 첨부한다.

     https://freestrokes.tistory.com/84