컬렉션_LinkedList

LinkedList 를 학습하기에 앞서, 배열의 장단점을 되짚어보자.

 

배열의 장점

- 배열은 구조가 간단하고 데이터를 읽는 데 (접근 시간) 걸리는 시간이 짧다. 

(주소값 1개에 동일 타입 데이터가 번호표 들고 있음.)

 

1

2

3

4

 

놀랍게도, 데이터 1과 데이터2에 접근하는 데 걸리는 시간이 같다.

????????????

어떻게 가능한가?

 

배열의 데이터에 접근하기 위해서는 아래와 같은 공식을 갖는다.

배열주소 + 데이터 크기 x (인덱스)

위의 예시에서는

동일한 배열에 존재하므로, 배열주소도 같고,

정수타입만 모아뒀으므로, 정수타입의 데이터 크기 4에

인덱스만 [0] , [4] 곱하면 되는 것이다.

따라서, 

01xx + 4*0 이나

01xx + 4*4 나 

접근하는 단계는 완전히 같으므로, 어디로 접근하든 접근에 걸리는 시간은 동일하다.

 

배열의 단점

1. 크기를 변경할 수 없다.

 - 크기를 변경하기 위해선 새로운 배열을 생성한 후 데이터를 복사, 붙여넣기 해야 한다. (까먹었다면 이전 글 ArrayList 를 보자.)

 - 크기 변경을 피하기 위해 처음부터 큰 배열을 생성하는 것도 방법이지만.. 쓸 지 안 쓸지도 모르는데 크게 만들면 낭비지.

 

2.비순차적인 데이터의 추가, 삭제에 시간이 많이 걸린다. 

 - 데이터를 추가하거나 삭제하기 위해, 다른 데이터를 옮겨야 함.

 - 순차적인 데이터 추가(끝에)와 삭제(끝부터)는 빠름. (데이터를 옮길 필요가 없으므로)

 

---

LinkedList 는 이러한 배열들의 단점을 보완한다.

1. 크기 변경 불가

2. 비순차적 데이터 추가, 삭제가 느림.

 

LinkedList

불연속적으로 존재하는 데이터를 연결(Link).

배열은 아래와 같이 연속적인 데이터들의 모음이다.

1

2

3

4

 

데이터 삭제

ArrayList 에서 중간 데이터를 삭제할 경우,

1. 지정 위치 다음 인덱스부터 끝까지의 배열을 복사 지정 데이터 위치부터 붙여넣기

2. 마지막 데이터 지우기 와 같은 과정을 거친다.

 

반면 LinkedList 의 경우,

1.단 한번의 참조 변경만으로 가능하다.

(삭제할 데이터의 참조값(다음 데이터의 주소값)을 삭제할 데이터 이전 데이터의 참조값으로 넣으면 끝.)

 

데이터의 복사, 붙여넣기 과정이 없다.

출처 - 남궁성 자바 기초편 LinkedList

 

 

LinkedList 를 구현하기 위해 사용된 개념은 Node 로 클래스로서 존재한다.

public class Node{
	Node next;
    Obejct obj;
}

Node

 - Node 는 다음으로 이어질 Node 에 대한 참조변수(주소값)을 가지고 있다.

 - Node 는 어떤 타입(Object)의 객체든 가질 수 있다.

 

데이터 추가

ArrayList 에서 중간에 데이터를 추가하기 위해서는,

1. 기존에 지정 위치에 있던 값 ~ 끝까지의 배열을 한칸 뒤로 이동(복사, 붙여넣기) (상황에 따라 더 큰 배열 생성)

2. 지정 위치에 새로운 데이터 추가 를 해야 했다.

 

반면,

LinkedList 는

1. 노드 생성

2. 지정 위치 이전 노드에 1에서 생성한 노드의 참조값 입력

3. 1에서 생성한 노드의 다음 노드 참조값 (next) 입력

만 하면 된다.

 

LinkedList 는ArrayList와 다르게,

1. 배열의 크기를 변경할 필요가 없다.

2. 중간 지점으로의 삽입, 삭제가 빠르다.

 

단점

다만, LinkedList는 데이터 접근성이 떨어진다는 단점을 지닌다.

Node0 -> Node1 -> Node2 -> Node3 -> Node 4-> Node 5 

와 같은 구조를 가지므로, Node4에 이르기 위해선 Node 0 ~ 3을 모두 거쳐야만 접근할 수 있기 때문이다.

 

이러한 접근성문제를 보완한 구조가 DoubleLinkedList 라고 한다.

DoubleLinkedList 는 서로 붙어있는 Node 들이 앞, 뒤로 이동할 수 있도록 했다는 모양.

class Node {
	Node next;
    Node previous;
    Obejct obj;
}

(멤버변수 하나 늘렸다고 참 편해진다.)

 

Doubly Circular Linked List

DoubleLinkedList 를 한 번 더 개선한 것이 Doubly Circular Linked List (이중 원형 연결 리스트 ) 라고 한다.

1. 노드끼리 앞 뒤로 연결

2. 맨 앞과, 맨 끝을 연결

(TV 채널 생각하면 쉽다.)

 

잠시 도랑으로 빠진 느낌이 드는데, 돌아와서..

Java에서는 Node가 Doubly Linked List 로 구현 됐다고 한다.

 

class LinkedList 에 있는 내부 클래스 Node 이다.

 

 

이상으로 LinkedList 에 대해 알아 보았다.

https://youtu.be/1ey5QpqbapU?si=tj9Hi_nd3TZsCKXQ