연결 리스트 - addFirst(), addLast()

addFirst 메서드
: 새로운 노드를 연결 리스트의 앞부분의 추가하는 방법

1. 새로운 노드를 만든다.
2. 새로운 노드의 next가 현재 head를 가리키도록 한다.
3. head 포인터가 다시 새로운 노드를 가리키도록 한다.

 

public void addFirst(E obj){
	Node<E> node = new Node<E>(obj);
    node.next = head; // 새로 생긴 노드의 next를 기존의 노드를 가리키는 head로 설정
    head = node; // 기존의 노드를 가리키는 head를 새로 생긴 노드를 가리키도록 설정
    currentSize++;
}

 

(두 번째 줄 왜 자꾸 공백이 들어가는,,,)
위의 순서는 잘 지켜줘야 한다.

head가 가리키는 값을 node로 바꾸는 것을 먼저 한다면, 기존에 있던 객체를 가리키는 포인터가 없기 때문에 가비지 컬렉션이 일어난다.

위의 코드는 여러 노드가 아닌, 추가할 부분의 앞쪽만 신경 쓰면 되기 때문에 시간 복잡도는 1이며,

아래의 경계 조건 다섯 가지를 고려해도 문제가 없다. 

 

https://paradiseiswhereiam.tistory.com/124

자료구조의 경계 조건

 

 

 

 

addLast 메소드
: 연결 리스트의 마지막을 가리키는 임시 포인터를 사용한다.
마지막을 가리키는 임시 포인터가 없으면 연결 리스트의 마지막 부분까지 도달하기 위해 next를 너무 많이 써야 하기 때문이다.

연결 리스트의 마지막 노드는 유일하게 next가 null을 가리키기 때문에

마지막을 가리키는 임시 포인터 tmp는 아래와 같이 작성한다. 

(마지막 노드로 향해야 하기 때문에 tmp.next를 tmp로 설정)

public void addLast(E obj){
	Node<E> tmp = head;
	while(tmp.next != null)
		tmp=tmp.next
	tmp.next=node;
}

문제1. 경계 조건
head가 비어있는 경우에는 tmp가 null이 되고 이에 따라 tmp.next도 null이 되어 NullPointException 에러가 발생한다.
리스트 맨 뒤에 요소를 추가하고 싶은데 비어 있는 리스트라면, addFirst 메소드처럼 그냥 노드를 추가한다.

public void addLast(E obj){
	Node<E> node = new Node<E>(obj);
	if (head == null){ // head가 비어있는 경우
		head=node;
		currentsize++;
		return;
	}
	Node<E> tmp = head;
	while(tmp.next != null)
		tmp=tmp.next
	tmp.next=node;
	currentsize++;
}

이때 currentSize == 0이 아니라 head == null로 조건을 건 이유는 currentSize 값을 바꿔야 하는데 실수로 바꾸지 않았을 때 문제가 생길 수 있기 때문에, 리스트가 비어 있음을 확실하게 보장 받을 수 있는 head == null로 확인한다.

문제2. 시간 복잡도
위처럼 tmp.next가 null인지 아닌지 하나하나 확인하다 보면 시간 복잡도는 O(n)이 된다.
하지만 처음부터 리스트의 마지막을 가리키는 포인터를 전역 변수로 설정한다면, 리스트의 마지막만 확인하여 시간 복잡도를 O(1)로 만들 수 있다. tail 포인터는 아래와 같이 설정한다.

public void addLast(E obj){
	Node<E> node = new Node<E>(obj);
	if (head == null){
		head=node;
		tail=node; // head 포인터뿐만 아니라 tail 포인터도 꼭 바꾸기
		currentsize++;
		return;
	}
	tail.next=node;
	tail = node;
	currentsize++;
}

 

 

 

 

참고

https://youtu.be/Pka_xr87Krg