연결리스트 맨 앞에 데이터를 추가하는 경우
- 리스트가 있고 연결리스트의 생성자를 호출할 때 가장 먼저 head를 null로 지정한다
- 이를 증가시킬 것인지 감소시킬 것인지 고려해야 한다
- 새로운 요소를 추가할 떄 data와 next를 가지고 있는 노드 클래스를 만든다
- 비어있는 연결리스트의 head를 가지고와서 새로 생성된 노드를 가리키도록 만든다
또 다른 노드 B를 추가할 때는 head의 값을 옮기기만 한다면 연결이 사라진 노드 A는 삭제된다
이를 방지하기 위해 새로운 노드를 추가할 때는, 새로운 노드를 기존 노드 A를 가리키게 하고
head를 새로운 노드 B를 가리키게 해야 데이터를 잃지 않고 추가할 수 있다
-> 맨 앞에 요소를 추가하면서 연결리스트의 크기를 늘렸다
새로운 요소를 추가하기 위해 뒷 부분을 살펴볼 필요가 없기 때문에
시간 복잡도 = 1이다
맨 앞에 추가하는 경우의 코드 (addFirst 사용)
public void addFirst(E obj) {
Node<E> node = new Node<E>(obj);
node.next = head; //head가 가리키는 곳 저장
head = node; //새로운 노드를 가리키게 한다
-> 이 두 코드의 순서는 꼭 지켜져야 한다
currentSize++; //새로운 요소를 추가할 때 값을 추가해줘야 함
}
* 요소를 추가할때마다 next를 추가하는 것은 확장성이 떨어져 비효율적이다(권장하지 않음)
head.next.next.next = node //임시포인터를 생성
tmp -> head를 가리킴
뒤에 노드가 있는지 어떻게 확인할 수 있는가?
null을 가리키고 있지 않는 것을 보고 확인가능하다
tmp.next != null //그 뒤에 노드가 더 있다는 것을 의미한다
tmp -> tmp.next 가리킨다
//while문에 할당
while(tmp.next != null)
tmp = tmp.next
-> tmp.next가 null이 아니면 계속 할당을 하고
null이 되면 할당을 멈춘다
코드
public void addLast(E obj) {
Node<E> tmp = head;
while(tmp.next != null)
tmp = tmp.next
tmp.next = node;
}
NullPointerException
런타임 에러
tmp가 null인데, tmp에 속해있는 next라는 변수를 불러오는 상황에서 발생한다
if (head == null) 리스트가 비어있는게 보장된다
head = node;
currentSize++;
addLast 메소드에서는 연결 리스트의 마지막을 가리키는 임시 포인터를 사용한다
-> 연결 리스트의 요소를 확인하려면 무조건 head에서 시작해야 하는데,
연결 리스트의 마지막까지 도달하는 데 next를 너무 많이 사용해야 하기 때문이다.
[경계 조건]
head가 비어있는 경우 tmp가 null이 되고, tmp.next를 찾지 못하는 NullPointerException 에러가 발생한다
리스트 맨 뒤에 추가하려 하는데 리스트가 비어있다면, 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++;
}
[시간 복잡도]
tail 포인터 사용하여 줄일 수 있다.
하나하나 살펴보면 O(n) 이지만 tail 포인터를 사용하면 O(1)으로 줄일 수 있다
리스트의 마지막을 가리키는 tail 포인터를 head, currentSize와 같은 전역 변수로 설정하고,
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++;
}
removeFirst 메서드
연결리스트의 메서드
노드를 제거하고 데이터에 저장된 객체를 반환해야 할 때,
첫 노드를 제거하기 위해 해야 될 것은 아래와 같다.
head에 head.next를 지정
head = head.next;
head -> null(비어있는 리스트)
이 head를 바로 head.next로 연결할 경우 NullPointerException이 발생한다
리스트가 비어있으면 null 반환
public E removeFirst() {
//리스트가 비어있는지 확인
if(head == null)
return null;
E tmp = head.data;
//요소를 추가할 때는 tail 포인터가 필요하다
요소가 한 개만 있을 때 tail과 head는 같은 것을 가리킨다
-> head와 tail 모두 변경해야 한다 -> 단점
리스트에 요소가 한 개인 사실을 어떻게 알 수 있을까?
- if(head.next == hull)
- if(currentSize == 1)
- if(head == tail)
위 세 개의 코드로 알 수 있다
최종코드
public E removeFirst() {
if(head == null)
return null;
E tmp = head.data;
if(head == tail)
head = tail = null;
else
head = head.next;
currentSize--;
return tmp;