1. LinkedList

• LinkedList는 Array를 이용하지 않은 List로, 데이터를 저장하고 있는 Node의 모음집이라 할 수 있다. 그래서 데이터가 메모리에 연속적으로 위치하지 않으며, 리사이즈도 필요 없다. 또한, ArrayList는 Index를 통한 접근이 가능했지만, LinkedList는 불가능하다.

• Node는 인스턴스로 데이터와 다음의 데이터를 가진 Node의 메모리 주소를 가진다.

• LinkedList는 최초의 Node를 저장하고 있는 메모리의 위치를 가지고 있어야 한다(head pointer).

• ArrayList는 시간 효율을 위해 데이터를 항상 뒤에 더했으나, LinkedList는 그와 반대로 앞에 데이터를 더하는 것이 일반적으로 더 효율적이다. 만약 뒤에 데이터를 더하려 한다면, 일반적으로는 최초 head로부터 다음 Node를 가지지 않은 Node까지 이동한 뒤에야 데이터를 추가할 수 있다.

• 데이터를 지우는 행위는 좀 더 복잡하다. 맨 뒤에서 데이터를 지우는 경우, 더하는 것과 마찬가지로 최후미의 Node 직전까지 이동한 후 Node의 다음 인스턴스를 null로 바꾸어주면, garbage collection에 의해 메모리 주소를 가리키는 것이 없어진 마지막 Node는 알아서 비워진다. 이를 이용하면, LinkedList를 통째로 지우기 위해서는, 각각의 Node를 일일이 해체하는 것이 아니라, 최초의 Node를 지정하는 head만 null로 바꿔주면 모두 비워진다.

• 데이터를 뒤로 계속 확장해야 할 필요가 있는 경우, head 처럼 tail 변수를 저장하면 더 편해진다. 관리를 위해서는 size 변수도 선언해줄 수 있다.

• head, tail, size가 모두 있다면, 데이터를 앞 또는 뒤에 더하는 행위는 항상 O(1), search와 뒤의 데이터를 지우는 행위는 O(n)이다.

2. 변형

• 위에서 설명한 LinkedList는 가장 일반적인 형태로, 정확히는 SinglyLinkedList라고 부른다. head 부터 tail까지 오직 한 방향으로만 움직일 수 있기 때문이다.

• 만약 Node가 다음 Node뿐만 아니라 직전의 Node 또한 가리키고 있다면, 양방향으로 움직일 수있고, 이를 DoublyLinkedList라고 한다. 이 경우, 저장해야하는 데이터가 늘어났기 때문에 공간 효율성은 떨어지지만, 양방향으로 움직일 수 있기 때문에 시간 복잡도는 일부 떨어진다. 예를 들어, 데이터를 뒤에서 지우는 행위는 이 경우 O(1)로 압축이 가능하다.

• 한편, LinkedList의 마지막 Node는 보통 next pointer가 null이지만, 이를 head를 가리키도록 할 수도 있다. 이 경우, CicularlyLinkedList라 부르며, single double 모두 가능하다. 시간 복잡도에 큰 변화는 없다.

3. Array&ArrayList와 LinkedList의 쓰임

• 상술한 3개의 자료구조는 그 자체로 데이터를 다루는 일에 직접 쓰이는 한편, 다른 자료구조를 구현하는 기초로 쓰이는 일이 많다.

• 둘 가운데 어떤 것을 기반으로 자료구조를 구현할지는, 구현해야할 자료구조의 특징에 따라 적합한 것을 선택한다.

출처: https://learning.edx.org/course/course-v1:GTx+CS1332xI+2T2020/home

이상의 내용은 edx 플랫폼을 통해 GTx에서 제공하는 Data Structures & Algorithms 강의의 내용을 개인적으로 정리한 것입니다. 그렇기 때문에, 부정확한 내용 혹은 잘못 이해하고 있는 내용이 있을 수 있으니 양해 부탁드립니다.