LinkedList 연결리스트
- 포인터를 사용하여 여러 개의 노드를 연결하는 자료 구조를 연결 리스트라고 한다
- 여러 개의 포인터를 사용해서 힙에 있는 여러 공간을 가리킨다
- 연결리스트에 데이터를 저장할 수 있는 변수를 만들고
- 모든 내용을 담아서 잘 작동하게 만드는 것은 어렵다
객체는 공간이 할당 되어있기 때문에 값에 비해 공간이 넓거나,
공간이 부족한 경우가 생긴다
연결리스트는 순차적인 데이터나 많은 양의 데이터가 있을때 특히 자주 사용된다
많은 양의 데이터를 적은 양의 메모리를 사용해서 저장할 수 있다
*기본적인 연결리스트의 내용
연결리스트 -> 노드를 사용
노드에는 두가지 정보가 있음 next라는 포인터와 할당된 데이터가 기본 구성 요소이다
이런 노드가 같은 방식으로 다량 만들어져있다 //data에는 정수가 들어간다
각각의 포인터는 메모리의 위치를 가리키고,(그래서 이름이 next) 다음 노드를 가리킨다
예) 노드 A는 노드 B, 노드 B는 노드 C를 가리킨다
마지막 노드의 next값은 null이다 //값이 없기 때문
next : 포인터 사실 data도 포인터이다 //어떤 객체를 가리키는 변수로 사용
연결리스트를 시작하는 시점 head
head는 리스트의 첫 번째 노드를 가리킨다
힙에서 이 연결리스트에 접근할 수 있는 유일한 방법은 head의 위치를 아는것이다
첫번째 노드의 next 포인터는 head.next로 나타낼 수 있고
이 데이터는 head.data로 나타낼 수 있다
head.data = 10;
head.next.data = 15; (노드 B의 데이터를 가리킴)
head.next.next (노드 B의 포인터를 가리키는 헤드)
하지만 연결 리스트의 길이가 매우 길 경우, 계속 head 뒤에 next를 붙일 수는 없다.
-> 임시포인터를 사용해서 연결리스트의 각 노드를 탐색하는 방법을 사용해야 한다
//링크드 리스트의 노드 객체를 의미하는 내부클래스
public class LinkedList<E> implements List1<E> {
class Node<E> { //내부 클래스로 next와 data를 가지고 있다
E data;
Node<E> next;
public Node(E obj) {
data = obj; //E라는 타입의 객체를 담고있음
next = null; //다른 노드를 가리키는 포인터
}
}
외부에서 노드의 포인터를 건드리지 못하게 하려면 어떻게 해야할까?
-> 내부클래스로 만들어서 이곳에서만 다룰 수 있도록 제한한다
private Node<E> head;
private int currentSize;
public LinkedList() { //연결리스트의 생성자
head = null;
currentSize = 0;
}
}
어떤 리스트를 가지고 있을 때
head 가 존재하고 노드들은 다음 노드를 가리킨다
연결리스트의 크기를 알고자 하는 경우 이 크기를 셀 때의 시간 복잡도
->요소가 n개일때 일일이 세는 경우 시간복잡도는 O(n)이다
currentSize라는 변수를 만들어서 리스트의 크기를 늘릴때마다
이 변수의 값도 늘리면 된다
이럴때의 시간 복잡도는 정확히 1이된다
-> 요소의 개수와 상관없이 무조건 현재 리스트의 개수를 알려주기 때문에
연결리스트를 사용할 때는 currentSize 변수를 할당하는 것이 좋다
자료구조들의 경계 조건
신경써야 할 경계조건은 5개가 있다
연결리스트 해시 트리 등 어느 자료구조든 해당되는 사항이다
- 자료 구조가 비어있는 경우 연결리스트에서 노드를 제거하여 비어있게 된다면 어떻게 처리해야하는가?
- 자료 구조에 단 하나의 요소가 들어있을 때 요소가 한 개만 있을때 요소를 제거하면 비어있게 된다
- 자료 구조의 첫 번째 요소를 제거하거나 추가할 때 자료구조의 맨 앞에 추가할때 헤드를 어떻게 할 것인지 고려해야 한다.
- 자료 구조의 마지막 요소를 제거하거나 추가할 때
- 자료 구조의 중간 부분을 처리할 때
자료구조를 만들 때 항상 고려 할 사항
- 연결 리스트의 메서드를 만들고 모든 경우의 메서드를 다룰 때 발생 할 상황을 고려해야 한다