LinkedList
LinkedList란
포인터를 사용하여 여러 개의 노드를 연결하는 자료 구조를 연결 리스트라고 합니다.
노드에는 두가지 구성이있습니다.
첫 번째는 인접한 노드를 가리키는 next라는 이름의 포인터, 두 번째는 우리가 노드에 넣는 데이터를 가리키는 포인터입니다. (노드 D의 경우, 다음에 아무것도 없기 때문에 null을 가리킵니다)
이 리스트는 head라는 이름의 포인터에서 시작합니다. Head는 리스트의 첫 번째 노드를 가리킵니다. 힙에서는 이 연결 리스트의 head만 알고 있기 때문에, head.next 혹은 head.data 등으로 노드의 내용을 찾습니다. 하지만 연결 리스트의 길이가 매우 길 경우, 계속 head 뒤에 next를 붙일 수는 없습니다. 그래서 임시 포인터를 사용하여 탐색하는 방법을 사용합니다.
배열과의 차이점
배열 또한 순서대로 여러 데이터를 저장할 때 사용한다는 공통점이 있습니다. 하지만 배열은 필요한 요소보다 너무 크게 만들거나 너무 작게 만들어 배열의 크기를 조정해야 한다는 문제점이 있습니다.
배열과 다르게, 연결 리스트는 항상 맞는 크기로 만들어지도록 설계되어 있습니다. 그래서 순차적인 데이터나 많은 양의 데이터가 있을 때 자주 사용됩니다.
노드와 크기
아래 코드는 LinkedList의 내부 클래스에서 노드를 정의한 내용입니다.
public class LinkedList <E> implements ListI<E>{
// 노드 정의
class Node<E>{
E data;
Node<E> next;
public Node(E obj){
data=obj;
next=null;
}
}
private Node<E> head;
private int currentSize;
public LinkedList(){
head=null;
currentsize=null;
}
}제네릭을 사용한 node클래스는
data라는 포인터와 next라는 node를 정의한 후, 생성자를 추가해 노드 객체를 완성했습니다.
생성자를 만들 땐 제네릭을 사용하지 않습니다.
생성자에서는 객체를 data에 저장하고 next는 우선 null로 지정합니다. 이 노드 객체는 내부 클래스이로만들어 외부에서 접근을 할 수 없도록 해야합니다.
외부에서 접근하게되면 노드들이 위치를 바꾸게 되고 결국 정보를 잃게 되기 때문입니다.
외부에서 접근하기 위해선 노드 객체를 만들 때와 같이 private 변수 head를 만듭니다.
노드의 개수를 세는 효율적인 방법
노드의 개수를 직접 세는 방법보다 int 타입인 변수 currentSize를 만들어 노드의 개수를 세는 방법이 더 효율적입니다.
currentSize를 만들어 논후 리스트에 요소가 추가될때마다 currentSize의 값을 늘리면 리스트의 크기를 바로 알수 있습니다.
경계조건
연결리스트를 사용하기위해 고려해야하는 조건들에대해 알아보겠습니다.
이 경계조건은 어떤 자료구조든 고려를 해야합니다.
1. 자료 구조가 비어있는 경우 2. 자료 구조에 단 하나의 요소가 들어있을 때 3. 자료 구조의 첫 번째 요소를 제거하거나 추가할 때 4. 자료 구조의 마지막 요소를 제거하거나 추가할 때 5. 자료 구조의 중간 부분을 처리할 때
addFirst 메소드
연결 리스트의 앞부분에 node를 추가하는 법에는 addFirst메소드를 사용하는 방법이있습니다.
1. 새로운 node를 만든다. 2. 새로운 node의 next가 현재 head를 가리키도록 한다. 3. head 포인터가 다시 새로운 노드를 가리키도록 한다.
head가 null인 연결리스트에 새로운 요소를 추가한다고 생각해보겠습니다.
next와 data를 가진 노드 클래스 객체가 먼저 생성되고, 연결리스트가 비어있으면 head를 가지고와서 새로 생성된 head는 새로 생성된 노드를 가르키게됩니다.
그림으로 그리면 다음과 같습니다.
그리고 또 다른 노드를 리스트 맨 앞에 추가한다고 생각해보겠습니다.
새로운 노드가 생겼으니 head가 새로운 노드를 가르키게 될까요?
이렇게 되면 아무도 A를 가르키고 있지 않아 GC가 일어나게됩니다.
앞서 설명했듯이 위 그림과 같은 상황이 일어나면 안되므로 새로운 노드가 생겼을땐 새로운 노드의 next도 A를 가르키게합니다.
그러고 나면 드디어 head를 옮길 수 있게됩니다.
결국 head는 B를 가르키고 B는 A를 가르키게됩니다.
이렇게 맨 앞에 요소를 추가하면서 연결리스트의 크기를 늘릴 수 있습니다.
이 작업의 시간 복잡도는 1입니다.
이 내용을 코드로 작성하면 다음과 같습니다.
public void addFirst(E obj){
Node<E> node = new Node<E>(obj); // 1 새로운 노드생성
node.next = head; // 2 위 그림에서 파란선
head = node; // 3 위 그림에서 빨간선
} 