본문 바로가기

Basic/자료구조,알고리즘

Linked list 와 Doubly linked list 의 개념과 차이점

반응형

1. Linked list 란


Array list의 경우 리스트의 엘리먼트가 배열의 엘리먼트인 반면에


linked list의 엘리먼트는 노드 객체를 사용 한다. 


그래서 엘리먼트(노드 객체)와 엘리먼트(노드 객체)를 연결(link),레퍼런스를 통해서 리스트를 구현


한 것을 의미한다. Linked list 에서는 이 연결이 중요하다!



2. 단방향 Linked list 의 구조  - 각 노드는 다음 노드를 가리킨다


 


Node객체 안에 변수들을 봐보자


1) Data field : 저장되는 실제 값을 가리킨다 - 노드의 값(보통 value라는 변수 사용)


2) Link field다음 노드의 참조값, 주소값(보통 next라는 변수 사용)을 가리킨다. 이렇게 링크 필드로 노드와 노드를 연결시키는 방법을 사용


3) head 변수 : 첫번째 노드를 가리킨다,첫번째 노드의 참조값( linked list 를 이용하려면 첫번째 노드를 알아야 다음 노드를 찾을수 있다)


4) tail 변수:  마지막 노드를 가리킨다.


5) size 변수 : 리스트안에 있는 엘리먼트, 노드의 수를 가리킨다.



3. Array list와 linked list의 차이점

  

 1) 데이터 조회 탐색의 효율성(메모리 구조)


    Array list는 달리 linked list는 특정 인덱스를 상수 시간에 접근 불가


    리스트에서 k번재 원소를 찾고싶다면 처음부터 k번 루프를 돌아야한다.


    즉, 최악의 경우 검색이 한쪽으로만 가능하기 때문에 노드 전체를 탐색해야 한다.






 2) 엘리먼트의 추가 삭제


Array list의 경우 추가/삭제가 느리다. 왜냐하면 엘리먼트를 처음과,중간에 추가/삭제할 경우


해당 엘리먼트의 뒤에 있는 모든 엘리먼트의 자리 이동이 필요하기때문이다.


아래 그림은 50을 추가 하기 위해 나머지 값들을 전부 뒤로 이동시키고 있다.




하지만 linked list의 경우, 상대적으로 추가/삭제가 될 엘리먼트의 이전, 이후 노드의 참조값(next)


만 변경하면 되기 때문에 속도가 빠르다.


아래 그림은 85를 추가시키기 위해 참조값만 변경시켰다.




4.  단방향 Linked list VS (양방향)Doubly linked list



 1) Doubly linked list 의 구조


Doubly linked list에서 각 노드는 다음 노드와 이전 노드를 가리킨다


단순 열결리스트 노드에서는 next 변수만 있었지만 이중 연결리스트에서는 prev 변수도 있다.



 2) 데이터 조회의 개선


단순 연결 리스트가 최악의 경우 검색이 한쪽으로만 가능하기 때문에 노드 전체를 탐색해야 


했던 것에 비해서 양방향 연결 리스트는 양쪽으로 검색이 되기 때문에 탐색해야하는 엘리먼트


가 반으로 줄어 든다.




조회하는 엘리먼트의 인덱스가 전체 size의 반보다 작다면 앞에서 부터 검색해가면서 


next변수를 활용하고 size의 반보다 크다면 뒤에서부터 prev변수를 활용한다.



 3) 메모리 사용 및 구현 복잡도


양방향 연결 리스트의 단점으로는 우선 이전 노드를 지정하기 위한 변수를 단방향과 달리 


나 더 사용해야 한다. 메모리를 더 많이 사용한다는 의미이다. 또 next와 prev변수를 활용해 양


방향으로 연결해줘야 해서 구현이 조금 더 복잡해진다


4) 데이터 추가 삭제 


 단방향 연결 리스트의 경우, 시작 지점에서 추가, 삭제 연산의 경우 상수 시간에 가능하다.


 그리고 끝 지점에서 추가 연산은 상수시간에 가능하나, 삭제 연산은 상수시간에 불가하다


 왜냐하면 양방향 연결리스트처럼 이전(prev) 노드로 알수 없기 때문이다.




             양방향 연결리스트의 경우 시작 끝 지점에서 추가,삭제 연산 모두 상수 시간에 가능 하다.



중간에 삭제하는 경우 양방향 연결리스트가 단방향 연결리스트 보다 빠르다. 탐색하는데 


시간이 적게 걸리기 때문이다.. 결론적으로 장단점은 존재하며, 자바 콜렉션 프레임워크에


서는 방향 연결리스트를 제공한다.



5. 리스트의 종류


1) 순차 리스트: 배열을 기반으로 구현된 리스트


2) 연결 리스트: 메모리의 동적 할당을 기반으로 구현된 리스트


6. 리스트의 선택


인덱스를 이용해서 데이터를 가져오는 것이 빈번하다면 ArrayList가 훨씬 빠르다.


하지만 데이터의 추가/삭제가 빈번하다면 LinkedList가 훨씬 효과적이다.


처리하고자 하는 데이터에 따라서 어떤 데이터 스트럭쳐를 선택할지를 잘 판단하는 것은


대규모 시스템을 구축하는데는 필수적인 능력이다.










반응형