[자료구조] LinkedList: 개념, 종류, ArrayList와의 차이점

반응형

 

Computer Science 모아보기 👉🏻 https://github.com/seoul-developer/CS

GitHub - seoul-developer/CS: 주니어 개발자를 위한 전공 지식 모음.zip

 

💋 개념

✔️ 정의

 

 

Linked List is a linear data structure, in which elements are not stored at a contiguous location, rather they are linked using pointers. Linked List forms a series of connected nodes, where each node stores the data and the address of the next node.

 

• 노드를 연결시키는 형태로 구현된 선형 데이터 구조
• 각 요소들은 불연속적인 메모리 위치에 저장된다! ⇒ 뿔뿔이 흩어져 있다.
• 각 노드는 데이터 + 다음 노드의 주소를 가진다.
• 자바의 자료구조인 LinkedList는 큐 ADT에 대한 구현체 중 하나다. 

 

 

✔️ 구성 요소

 

• Node Structure: 하나의 노드에는 2개의 요소가 있다.
• Data: 데이터의 실제 값
• Next Pointer: 다음 노드의 메모리 주소
• Head and Tail: Head 노드(리스트에서 첫번째 노드)와 Tail 노드(리스트에서 마지막 노드)의 위치
• 마지막 노드의 Next Pointer는 NULL or nullptr를 가리키는데, 이게 Tail 노드라는 의미다.

 

 

💋 종류

✔️ Sinle linked list

 

• 각 노드는 데이터 + 다음 노드의 주소를 가진다.
• 탐색은 한방향으로만

 

 

✔️ Double linked list

 

• 각 노드는 이전 노드의 주소 + 데이터 + 다음 노드의 주소를 가진다.
• 양방향 탐색 가능하지만, 추가적으로 저장해야 하는 주소가 상당해서 메모리 관점에서는 ㅠㅠ

 

 

✔️ Circular linked list

 

• 마지막 노드가 다시 첫번째 노드의 주소를 가지고 있어서, 빙글빙글
• 그림에서는 단방향이지만, Double linked list처럼 양방향으로 빙글빙글할 수도 있다.

 

 

 

💋 연산

LinkedList의 연산에서, 데이터 삭제나 삽입은 빠르지만, 탐색하는 과정이 상대적으로 느리다.

 

✔️ 삽입(Insertion)

 

삽입을 원하는 위치에서 인접한 노드의 next pointer 값만 변경해주면 되기 때문에 매우 빠르다. ⇒ O(1) 시간 복잡도

 

 

 

✔️ 삭제(Deletion)

 

삽입과 마찬가지로, 삭제할 노드와 인접한 노드의 next pointer 값만 적절하게 변경해주면 되기 때문에 빠르다. ⇒ O(1) 시간 복잡도

 

 

✔️ 검색(Searching)

LinkedList는 데이터가 메모리에 순서대로 저장되어 있는 것이 아니고, 흩어져 있기 때문에 Head Node부터 시작해서 모든 노드를 순차적으로 탐색해야 한다. ⇒ O(n)의 시간복잡도

 

리스트의 크기에 비례해서 탐색 시간은 늘어날 수 있다.

 

 

💋 ArrayList vs LinkedList

 

ArrayList는 지난 포스팅에서 설명한 동적 배열의 구현체다.

LinkedList도 지난 포스팅에서 설명한 Linked List ADT의 구현체다.

 

✔️ 차이점

 

두 가지의 가장 큰 차이점은 메모리에 어떻게 저장되는가이다.

 

• ArrayList: 배열의 한 종류로, 연속적인 메모리 공간에 저장됨.
• LinkedList: 노드 각각이 pointer 형태로 다음 노드의 주소를 가리키는 형태로 메모리 공간에서 띄엄띄엄 저장됨

 

✔️ 비교

 

 

💋 그래서 LinkedList는 언제 쓰는게 좋은건데?

 

조금만 공부해봐도 LinkedList는 배열에 비해서, 순차적으로 탐색하는 과정이 느리고, 데이터의 삽입과 삭제는 빠르다. 그치만, 까먹어서는 안되는 건 데이터와 삽입과 삭제 행위 자체가 빠르다는거지, target 위치까지 가기 위해서는 여전히 탐색이 필요할 때가 많다.

 

그래서 자바에서 LinkedList를 만들었다는 분의 트위터 글도 유명하다.

 

 

 

실제 구현을 찾아보지는 않았지만, ArrayList의 구현은 Java 표준 라이브러리에서 지속적으로 개선되고 있어서 요즘은 저렇게 무식하게 다 복사하고 이런 방식보다 더 효율적으로 JIT 컴파일러 최적화라던가, 전체가 아니라 배열을 부분적으로만 복사하는 방법이라던가, 더 고성능의 자료구조나 알고리즘을 사용해 성능을 최적화하고 있다고 한다. ⇒ ArrayList 이 발전하고 있다!

 

물론 LinkedList도 next node의 주소를 추가적으로 저장해야 하기 때문에 데이터적으로 마이너스지만, 꾸준히 성능을 개선해왔기 때문에 현재 두 가지의 성능 차이는 그닥 유의미한 것 같지는 않다.

 

그럼에도 두 가지의 성능을 시간 기준의 시간 복잡도로 비교해보면 다음과 같다.

 

(아래에 한글로 정리해놨음!)

 

 

 

1. 데이터 삽입 및 삭제:
• ArrayList: 특정 인덱스에 데이터를 삽입하거나 삭제할 경우, 해당 인덱스 이후의 모든 요소를 이동시켜야 함으로 시간이 많이 소요될 수 있다. ⇒ 시간 복잡도는 O(n)
• LinkedList: 데이터를 삽입하거나 삭제할 때, 단순히 앞뒤 노드의 포인터만 조정하면 되므로 ArrayList보다 빠르다. ⇒ 시간 복잡도는 O(1)
2. 데이터 접근:
• ArrayList: 인덱스 기반으로 탐색하기 때문에, 데이터에 빠르게 접근할 수 있다. ⇒ 시간 복잡도는 O(1)
• LinkedList: 특정 인덱스에 직접 접근하기 위해서는 처음부터 해당 인덱스까지 포인터를 따라가야 하므로 ArrayList보다 느리다. ⇒ 시간 복잡도는 O(n)

 

 

그냥 모르겠을 땐 ArrayList를 쓰라고도 한다. 이게 오늘 내가 내릴 수 있는 결론이었다!

 

 

 

💋 참고자료

• https://medium.com/javarevisited/linked-list-analysis-java-developers-should-know-121ed803bee1
• https://stackoverflow.com/questions/322715/when-to-use-linkedlist-over-arraylist-in-java
• https://javarevisited.blogspot.com/2012/02/difference-between-linkedlist-vs.html#axzz5hP3QBNdL
• https://www.youtube.com/watch?v=xvi-n11kym0&list=PLcXyemr8ZeoR82N8uZuG9xVrFIfdnLd72&index=4
• https://afteracademy.com/blog/types-of-linked-list-and-operation-on-linked-list/
• https://www.geeksforgeeks.org/applications-advantages-and-disadvantages-of-linked-list/

도움이 되었다면, 공감/댓글을 달아주면 깃짱에게 큰 힘이 됩니다!🌟
비밀댓글과 메일을 통해 오는 개인적인 질문은 받지 않고 있습니다. 꼭 공개댓글로 남겨주세요!