연결리스트(LinkedList)

연결리스트란?

배열의 단점을 보완 시킨 형태.

배열은 크기를 변경할 수 없고 비순차적 데이터의 추가 및 삭제가 어려운 단점이 있다.

(배열은 순차적(연속적) 데이터의 관리에 용이함)

이를 보완하기 위해 고안된 형태가 연결리스트(LinkedList)라고 볼 수 있다.

 

이 둘을 그림으로 비교해 보면,

비연속적 특징을 띄는 LinkedList

연결리스트의 포함요소

배열은 그림과 같이 데이터만을 담고 연속성을 띄고 있는데

연결리스트는 두개의 칸으로 나뉘어 노드로 표현 돼 있는걸 볼 수 있다.

 

노드란 ? 
비연속성의 띄는 연결리스트에서 다음의 데이터가 어디있는지를 알려주는 요소이다.
(배열과 같이 연속성을 띄는 형태에선 자신의 옆이 바로 다음의 요소인걸 알기에 노드가 필요치 않다.)

class Node {
        Node    next;  // 다음 요소의 주소를 저장
        Object obj;     // 데이터를 저장

간단하게 위의 그림에서 연결리스트의 한칸 한칸이 노드이며 그중 위에 있는 부분은 포인터로 불리며 다음 노드를 가르키는 주소가, 아래칸은 요소(데이터)가 담겨 있다.

연결리스트의 장점

얼핏 보면 배열 처럼 연속성의 띄는 형태가 데이터 관리를 더 편하게 할 수 있을 것 같지만,

(배열은 크기가 정해져 있어 추가 작업을 하려면 새로 만들어야한다)

데이터의 추가 및 삭제는 비연속성을 띄는 연결리스트가 더 편리하다.

데이터의 삭제

데이터의 추가

배열과 달리 연결리스트의 크기는 정해져있지 않기에 이와같은 동작이 가능하다.

 

연결리스트의 메서드

- 연결리스트 객체 생성방법

LinkedList list = new LinkedList();

 

1. 값 추가 메서드

- list.addFirst() :  가장 앞에 데이터 추가

- list.addLast() :  가장 뒤에 데이터 추가

- list.add(index, data) : index 위치에 데이터 추가(index 미표기시 가장 뒤에 데이터 추가)

 

2. 값 삭제 메서드

- list.removeFirst() : 가장 앞의 데이터 제거- list.removeLast() : 가장 뒤의 데이터 제거- list.remove(index) : index 위치의 데이터 제거(index 미표기시 가장 앞의 데이터 제거)

- list.clear() : 모든 데이터 제거

 

3. 값 출력

- list.get(index) : index의 데이터 얻기