8주차, 자료구조 연결 리스트(Linked List)

1. 설명

Linked List 는 Node라는 객체로 구성되어 있다.

노드는 데이터를 저장할 수 있는 필드와 다음 노드를 가르키는 넥스트 포인터를 가지고 있다.

이 노드들이 다 연결된 형태를 Linked List 라고 한다.

 

가장 앞에 있는 노드를 헤드, 끝의 노드를 테일이라 한다. 테일의 넥스트 포인터는 Null이다.

 

검색의 경우, 인덱스가 없기에 랜덤 엑세스를 할 수 없다.

 

N개의 노드를 가지고 있는 노드를 검색할 때, 시간복잡도는 O(N)이다. 헤드부터 테일까지 뒤져봐야

하기 때문이다.

 

추가의 경우, O(N)의 시간을 사용해서 테일까지 찾아가서 추가한다.

 

삽입의 경우, 중간에 끼워놓고 포인터만 바꿔주면 된다. 하지만 삽입할 곳 까지 찾아가야 하니 시간복잡도는

O(N)이다.

 

이전(Previous) 노드가 가르키는 방향을 삽입할 노드로 설정하고, 삽입한 노드의 넥스트포인트를

Next 노드로 설정한다.

 

헤드에 삽입할 경우, 새로 삽입된 헤더의 넥스트포인터만 설정하면 되니 매우 간편하다.

 

삭제의 경우, ArrayList의 경우, 삭제한 인덱스 뒤에 있는 걸 다 당겨와야 하니 O(N)의 시간복잡도를

사용하지만 LinkedList는 포인터만 바꿔주면 삭제가 가능하다.

삭제할 노드의 Previous 노드의 넥스트포인터를 Next노드로 설정해주면, 중간에 있던 노드는 아무도

참조하지 않으니 자바의 Garbage Collecter가 수거해간다.

 

LinkedList의 장점은 

・ 배열의 복사나 재할당 없이 데이터 추가 가능 // ArrayList의 경우 배열이 꽉 차면 데이터를 늘려주고

// 기존에 있던 데이터를 추가하는 작업이 필요하다. 그리고 Array의 경우 배열이 한번 늘어나고

// 이제 그 공간에 작은 데이터만 들어가 있어도 그 뒤에있는 메모리는 소비하고 있다. Linked는 쓸만큼만 씀

 

・ 유연한 공간 // 애초에 배열 크기를 선언할 필요가 없다.

 

LinkedList의 단점

・ 데이터 접근에 대한 시간 증가 // 랜덤 액세스가 안되니 뭘 찾아가도 O(N)의 시간이 걸린다.

 

2. ArrayList와 LinkedList의 시간 비교

          LinkedList       ArrayList

추가     O(N)              O(1), O(N)    // Array의 경우 배열이 꽉 차서 재할당할 경우 O(N)     

삽입     O(N)                    O(N)      // Linked는 그 데이터를 찾아야 하니 O(N)이고, Array는 

                                                     // 찾는 건 O(1)이지만 뒤에 데이터를 하나씩 미는 작업이 O(N)

삭제     O(1)                     O(N)    // Array의 경우 뒤에 데이터를 앞으로 하나씩 당겨와야하니 O(N)

검색     O(N)                    O(1)

 

읽는 용도로 자주 쓰면 ArrayList, 추가 삭제 등 변경이 많을 것 같으면 LinkedList를 쓰는 게 효율적이다.