[Java] LinkedList 특징

목차

• 배열의 장단점
• LinkedList 특징
• LinkedList 종류
• ArrayList vs LinkedList 성능비교

 

배열의 장단점

 

장점

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

놀랍게도 배열의 첫 번째 요소를 읽는 시간과 마지막 요소를 읽는 시간은 똑같다.

인덱스가 n인 데이터의 주소 = 배열의 주소 + n * 데이터의 크기

 

 

단점

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

• 크기를 변경해야 하는 경우 새로운 배열을 생성 후 데이터를 복사해야 함.
• 그렇다고 크기의 변경을 피하기 위해 충분히 큰 배열을 생성하면, 메모리가 낭비됨.

1. 더 큰 배열을 만든다.
2. 기존 내용 복사
3. 참조를 변경해야 한다.

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

• 배열 중간에 있는 데이터를 추가, 삭제 할 때 뒤에 있는 다른 데이터의 자리를 옮겨야 하기 때문에

 

그러나 순차적인 데이터 추가(끝에 추가)와 삭제(끝부터 삭제)는 빠르다.

• 데이터 이동이 없기 때문에

 

 

 

LinkedList - 배열의 단점을 보완

• 배열과 달리 링크드 리스트는 불연속적으로 존재하는 데이터를 연결(link)
• 불연속적으로 존재하는 각 요소를 노드라고 불름.
• 하나의 개별요소(노드)를 연결해놨기 떄문에 변경에 유리하다는 장점이 있다.
• 노드에는 다음노드(참조변수)와 데이터(배열의 데이터)를 가지고 있음.

class Node {
    Node next; // 다음 노드의 참조값
    Object obj; // 데이터
}

 

 

 

데이터의 삭제: 단 한 번의 참조변경만으로 가능(다음 노드 참조변수의 값을 바꿈)

 

 

 

 

 

데이터의 삽입: 한 번의 Node 객체생성과 두번의 참조변경만으로 가능

 

 

 

 

 

 

LinkedList - 이중 연결 리스트

링크드 리스트(linked list):  연결리스트, 데이터 접근성이 나쁨(불연속적)

한번에 못간다. 왜냐하면 N번째 요소는 다음번 째 요소의 참조주소만 알고 있기 때문이다.

그래서 배열처럼 한번에 이동이 불가능하다. 징검다리처럼 한 다리 한 다리씩 건너야 한다.

 

 

더블리 링크드 리스트(doubly linked list): 이중 연결리스트, 접근성 향상

앞 뒤로 이동을 할 수 있어 좀 더 접근성이 향상 되었다.

대신 추가하거나, 삭제할 때도 두개씩 참조변경 해줘야한다.

한번에 두,세 개씩 뛰어넘진 못한다.

class Node {
    Node next; // 다음 노드의 참조값
    Node previous; // 앞 노드 참조값
    Object obj; // 데이터
}

 

 

 

더블리 써큘러 링크드 리스트(doubly circular linked list): 이중 원형 연결리스트

첫 요소가 이전 요소로 가면 맨 끝 요소까지 한 번에 갈 수 있게 되었다.

(CH.1  에서 채널을 내리면 CH.999)

 

참고: 실제 자바에서는 이중 연결 리스트로 되어있다. 여전히 베열에 비해서는 접근성이 나쁘다.

 

 

ArrayList(배열기반) vs LinkedList (연결 기반) 성능비교

1. 순차적으로 데이터를 추가/삭제: ArrayList가 빠름

2. 비순차적으로 데이터를 추가/삭제: LinkedList가 빠름

3. 접근시간(access time): ArrayList가 빠름