연결 리스트 Linked List

연결 리스트

 

연결 리스트의 기본 구성 요소는 노드라는 작은 블록이다.
노드에는 인접한 노드를 가리키는 next라는 이름의 포인터와 우리가 노드에 넣는 데이터를 가리키는 포인터 총 2가지 정보가 들어 있다.
마지막 노드의 경우, next는 null을 가리키고 있다.

포인터는 어떤 공간을 가리키는 것이다.
위에서 말한 데이터도 사실은 포인터이다.
어떤 객체의 요소를 가리키는 것이다.

리스트는 head라는 이름으로 시작한다.
head는 리스트의 첫 번째 노드를 가리킨다.
힙에서는 이 연결 리스트의 head만 알고 있기 때문에, head.next, head.data 이런 식으로 노드의 내용을 찾는다.
연결 리스트의 길이가 길다면,
head.next.next.next... next와 같이 찾는다는 듯이다.

하지만 이 방법에는 무리가 있으므로, 임시 포인터를 사용하여 탐색하는 방법을 사용한다.

배열과의 차이점

배열 : 순서대로 여러 데이터를 저장할 때 사용.
그러나 생성 시 설정한 크기와 데이터의 크기가 안 맞아서 에러가 뜰 때가 종종 있다.
ex. 배열 크기는 10인데 데이터는 1만큼만 있어 자리를 낭비하게 되는 경우 혹은 데이터가 11만큼 들어와 예외가 뜨는 경우

연결 리스트는 항상 맞는 크기로 만들어지도록 설계돼있음 
- 순차적인 데이터나 많은양의 데이터가 잇을 때 특히 자주 사용됨
많은양 데이터를 적은 메모리로 사용 ㄱㄴ

 

 

연결 리스트의 내부 클래스에서 노드를 정의할 때는 아래와 같다.

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=0;
	}
}

 

노드는 next라는 다음 노드를 가리키는 포인터와 data를 가진다.

data의 자료형 ➡️ E : 아직 자료형이 정해지지 않음. 이 연결 리스트를 사용할 때 지정하겠다는 뜻.
next의 자료형 ➡️ Node : 다음 노드를 가리키는 포인터이기 때문.

생성자 : 생성자까지 적으면 노드 객체가 완성된다. 생성자에서는 객체를 data에 저장하고 next는 우선 null로 지정.

이 노드 객체는 내부 클래스라서 연결 리스트가 아닌 다른 곳에서는 접근할 수 없다.

data와 next는 다른 곳에서 접근할 수 있도록 두면 외부에서 값을 바꿀 수 있기 때문에 이를 보호하기 위해 private 변수 head를 만든다. 이 변수로만 접근이 가능하다.


노드의 개수 세기
노드의 개수를 직접 셀 때의 시간 복잡도 : O(n)
currentSize라는 변수를 만들어 리스트에 요소를 추가할 때마다 currentSize값을 늘릴 때의 시간 복잡도 : 1

그냥 currentSize를 찾아보면 되므로 후자가 훨씬 효율적이다.