2주차-연결리스트
리스트가 있고,생성자로 연결리스트를 생성하는 경우!
- 포인터
2-4. addFirst 메소드(새로운 Node를 연결리스트 맨 앞에 추가하는 경우)
- Node 생성 후, next(그 다음 노드를 가리키는 포인터)에 head를 가리킨다. 여기서 head의 포인터는 새 노드가 형성할 때 그 노드를 가리킴
<코드>
public void addFirst(E obj){ // 내부 클래스
Node<E> node = new Node<E>(obj); // 새 노드 생성
node.next = head; // 항상 head의 주소를 새 노드에 넣는다 => 새 노드는 원래 첫번째 노드에 연결됌
head = node; // head가 새 노드의 주소값을 받아 지정
currentSize++; //연결리스트의 크기(Node 갯수)
}=> 위 코드는 앞 부분만 신경 쓰면 된다. 그러므로 한 번만(앞부분) 작동해 시간복잡도는 O(1).
*주의!!!
- if 비어있는 연결리스트인 경우
이때, head는 null을 가리킴
-비어있는 연결리스트에 새 노드가 형성되면, head의 포인터는 새 노드를 카리킨다(관계만 변해서 연결리스트 내에 문제는 발생하지 않는다)
-경계조건에 문제X
-생각해보기 - head가 비어있는 경우, 즉 head가 null을 가리키는 경우에 addFirst 메소드를 사용하면 node.next, head가 어떻게 달라지나요?
2-5. addLast 메소드(연결리스트 맨 뒤에 추가하는 경우)
ex)
*AddLast메소드 행동양식
(1) temp(연결리스트의 마지막을 가리키는 임시포인터)을 생성
생성 이유 - 연결리스트이 요소를 파악할 때 무조건 head에서 시작하여 작업속도가 느려짐
*연결리스트의 마지막 노드는 유일하게 next가 null을 담는다. 이로 인해 next가 null이 담겨 있는가로 마지막 노드인지 판단 가능하다!
<temp 선언 코드>
Node<E> tmp = head;(2) temp가 null을 담지 않게 끊고서 다음 노드를 가리킨다
-temp(임시포인터)을 가지고 마지막 노드의 포인터를 가진 노드를 가리키게 만든 뒤, 그 노드의 포인터는 마지막 노드를 가리킨다
<코드>
temp.next != null; // temp.next = null이 아니므로 뒤에 새 노드 존재함을 의미
temp = temp.next; // temp는 노드를 가리킴
temp.next = node; // temp.next가 뒤의 새 노드를 가리킴총정리
public void addLast(E obj){
Node<E> tmp = head;
while(tmp.next != null)
tmp=tmp.next
tmp.next=node;
}- 메소드 사용 시 경계조건&시간복잡도 -> 범위를 벗어나 가비지 컬렉션이 발생!
(가바지 컬렉션 발생시,
-가비지 컬렉션(GC)이 동작하는 동안에는 다른 동작을 멈추기 때문에 오버헤드가 발생!)
(1) 경계조건
-head가 비어있는 경우: temp = null이 되어 temp.next를 찾지 못해 NullPointerException 에러 발생
<에러 발생를 막기 위한 addLast 메소드>
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++;
}(2) 시간복잡도
- 연결리스트의 마지막 노드를 찾을 때, 맨 앞부터 찾는 경우 시간복잡도는 O(n)
=>이를 해결하기 위해 temp이나 tail이라는 포인터를 사용한다(이 경우, 시간복잡도는 O(1))
<시간복잡도 고려한 addLast 메소드 총정리>
public void addLast(E obj){
Node<E> node = new Node<E>(obj);
if (head == null){// head가 비어있는 경우
head=node;
tail=node; // tail 포인터도 null이 아닌 node를 가리킴
currentsize++;
return;
}
tail.next=node;
tail = node;
currentsize++;
}
*리스트가 비어있으면 head,tail 모두 바꿔야 한다
*tail을 움직일 때 시간복잡도가 발생하나, tail를 사용하는 편이 더 효율적
*메소드는 LinkedList란 클래스 내부에 존재한다
*생각해보기 - 왜 currentSize 변수 대신 tail 포인터를 사용하나요?
=>currentSize를 갱신하는 경우를 까먹는 경우가 발생하여 에러가 발생하거나 잘못된 노드가 선택될 수 있기 때문
2-6. removeFirst 메소드
-> head = head.next를 하는 것만으로 처리되지만, 경계조건에서 에러가 발생!
- 경계조건1 - 자료구조가 비어있는 경우
->'head.next = null'이 되어 NullPointerException에러 발생
해결방안) null 반환(by Javadoc)
*NoSuchElementException이란?
<코드>
public E removefirst(){
// 경계 조건 1
if (head == null)
return null;
E tmp = head.data;
head = null;
tail = null;
// 그 외의 경우
else
head = head.next;
currentSize--;
}- 경계조건2 - 자료구조에 단 하나만 있는 경우
-> head와 tail이 같은 경우, 첫 노드가 가비지 컬렉션이 되어 에러 발생
해결방안)'head = null; tail = null'로 초기화
*노드가 1개임을 증명하는 방법
-head.next가 null을 가리키는가
-currentSize = 1
-head=tail
<코드>
public E removefirst(){
E tmp = head.data;
// 경계 조건 2
if (head == tail) // head.next == null, currentSize == 1도 가능
head = null; // head = head.next과 같다
tail = null;
// 그 외의 경우 - 에러 발생X
else
head = head.next;
currentSize--;
}총정리
public E removefirst(){
// 경계 조건 1
if (head == null)
return null;
E tmp = head.data;
// 경계 조건 2
if (head == tail) // head.next == null, currentSize == 1도 가능
head = null;
tail = null;
// 그 외의 경우
else
head = head.next;
currentSize--;
}*생각해보기-tail 포인터의 단점은 무엇인가요?
=>노드를 삭제나 추가하는 경우 신경써야하는 영역이 늘어나 코드의 복잡성이 올라감
2-7. removeLast 메소드
->마지막에서 2번째 노드를 찾아 옮긴 뒤, 연결리스트의 마지막 노드 제거
*제거 방법
(1) 임시 포인터 두 개(current,previous) 생성
<결과>
<코드>
Node<E> current = head,
Node<E> previous = null;(2) current의 포인터는 현위치, previous의 포인터는 이전 위치 가리킴
<결과>
<코드>
while (current != tail) {
previous = current;
current = current.next;
}(3) 연결리스트의 끝에 도달하면(previous의 포인터는 마지막에서 2번째 노드를 가리킨다)작업 끝!
*연결리시트의 끝임을 아는 방법
-current == tail
-current.next == null => 이 경우, NullPointerException에러 발생 가능
*경계조건
->에러 해결용 추가 코드
-removeFirst메소드와 같은 경우에 에러가 발생하며, 똑같이 예외 처리
총정리
public E removeLast(){
// 자료 구조가 비어있는 경우
if (head == null)
return null;
// 자료 구조에 단 하나의 요소가 들어있을 때
if (head == tail)
return removeFirst();
// 그 외의 경우
// 임시 포인터 current, previous를 활용하여 마지막 노드를 제거
Node<E> current = head; // Node current = head;
Node<E> previous = null; // Node previous = null;
while (current != tail) {
previous = current;
current = current.next;
}
previous.next = null;
// 안하면 head,tail 각각의 연결리스트 생성하여 정리해야 한다
tail = previous;
currentSize--;
return current.data;
}생각해보기)currentSize가 (연결 리스트의 크기) - 1이 되는 지점을 찾는 방식으로 마지막에서 2번째 노드를 찾을 수도 있습니다. 이 방법과 임시 포인터를 사용하는 방법 중 어떤 것이 효율적인가요?
