Java 자료구조 List (3) LinkedList 뜯어버려!
LinkedList 뜯어보기
- LinkedList가 어떻게 구체적으로 다른지 알아보자
LinkedList
구조
그림정리
- 기본구조
- 노드라는 객체로 되어있음
- 데이터를 저장할 수 있는 필드와 다음 노드를 가리키는 넥스트포인트를 가지고 있다.
- 이 노드들이 다 연결된 형태를 LinkedList라고 함
- 가장 앞이 헤드 뒤가 테일이다.
- 검색
- ArrayList와는 다르게 index 를 통한 랜덤 엑세스가 불가능함
- nextPointer 로만 접근가능
- 시간 복잡도는 O(N) -> 처음부터 Null 까지 찾은 후 그 다음에 데이터가 추가되기 때문
- 삽입
- 인덱스를 바꿔줄 필요는 없음
- 포인터를 바꿔주면 됨
- 헤드부분에 데이터를 삽입할 경우는 ArrayList 는 인덱스를 다시 뒤로 밀어줘야해서 N번 작업해야되서 시간 복잡도는 O(N)
- 하지만 LinkedList는 앞에다가만 넣어주면 되고 다른 작업이 필요없음
- 삭제
- 중간의 데이터를 삭제할 경우
- 예를 들어 1번 2번 3번 이렇게 연결되어 있고 2번 데이터를 삭제한다면
- 1번 포인터를 3번으로 지정해주면 끝
- 이 때 2번은 가비지 콜렉터가 가져감
- 중간의 데이터를 삭제할 경우
- 장점
- 배열의 복사나 재할당없이 데이터 추가 가능
- 유연한 공간
- 단점
- 데이터 접근에 대한 시간이 늘어남 O(N)
코드로 구현해 보기
- 헤드 더미 노드 사용
- 헤드부분부터 데이터를 넣는게 아니라 헤드부분에 더미 노드를 만들어서 어떤상황에서도 헤드부분은 비어있는 상태로 만듦
- 데이터가 없어도 마찬가지
- 그냥 사용할 경우 if문 처리나 특이 케이스에서 귀찮아짐
- 그리고 코드구현에 있어서 좀 더 간결해짐
package list;
public interface IList<T> {
void add(T t);
void insert(int index, T t);
void clear();
boolean delete(T t);
boolean deleteByIndex(int index);
T get(int index);
int indexOf(T t);
boolean isEmpty();
boolean contains(T t);
int size();
}
package list;
public class MyLinkedList<T> implements IList<T> {
private int size; // 몇 개의 데이터를 갖고 있는지에 대한 사이즈
private Node head; // head 노드
public MyLinkedList() {
// MyLinkedList 초기화
this.size = 0;
this.head = new Node(null); // 노드 초기화 (더미노드)
}
@Override
public void add(T t) {
Node current = this.head;
while (current.next != null) {
current = current.next;
// 마지막 노드의 끝이 null 이 될때까지 계속 확인
// 노드의 끝이 null 이라면 그 노드는 마자믹 노드임
}
Node n = new Node(t);
current.next = n; // 마지막 노드에 데이터 넣어줌
// linkedList는 next 와 next로 연결되어있음
this.size++;
}
@Override
public void insert(int index, T t) {
if (index > this.size || index < 0) {
throw new IndexOutOfBoundsException();
}
Node prev = this.head; // 맨 처음 노드로 옮
Node current = prev.next; // 헤드노드의 노드의 바로 뒤가 current
// 노드 첫 번째가 head , 두 번째가 current
int i = 0;
while (i++ < index) {
// 0 번째 부터 해당 index까지 순차적으로 이동
prev = prev.next;
current = current.next;
}
Node newNode = new Node(t, current);
// 새로운 노드 생성 -> t는 데이터,
// current는 현재 newNode 다음을 가르킬 노드
prev.next = newNode;
// newNode 앞에 올 데이터
// 1, 2, 3 이렇게 있다고 치고
// 1과 2 사이에 6이라는 데이터가 들어간다고 가정한다면
// 1 다음에 6을 가르키게 하는 작업임
this.size++;
// 데이터가 추가되었으니 (1개) 사이즈도 1개 올리기.
}
@Override
public void clear() {
this.size = 0;
this.head.next = null;
// 사이즈를 0으로 만들고 head가 다음을 가르키는게 없게 만들면 된다.
}
@Override
public boolean delete(T t) {
Node prev = this.head;
Node current = prev.next;
while (current != null) {
if (current.data.equals(t)) {
// current에 있는 data가 입력받은 데이터 t와 같은지 검사
prev.next = current.next;
// 연결을 끊는 작업
// 1, 2, 3 이 있고 2를 삭제하고 싶다면
// 1의 다음을 2의 다음 3으로 연결 시킴
current.next = null;
// 2의 다음은 null 처리해서 삭제
this.size--;
return true;
}
// 위의 조건식 검사가 진행되지 않을 경우 밑에 코드가 계속 진행
prev = prev.next;
current = current.next;
}
return false;
}
@Override
public boolean deleteByIndex(int index) {
if (index >= this.size || index < 0) {
throw new IndexOutOfBoundsException();
}
Node prev = this.head;
Node current = prev.next;
int i = 0;
while (i++ < index) {
// index 값을 찾을 때까지 0부터 계속 진행됨
prev = prev.next;
current = current.next;
}
prev.next = current.next;
// 기존의 연결을 끊고 기존의 다음 node에 연결
current.next = null;
// 현재 노드에서 다음 노드와의 연결을 끊음
this.size--;
// 연결된 데이터가 1개 없어졌으니 사이즈도 1개 축소
return true; }
@Override
public T get(int index) {
if (index >= this.size || index < 0) {
throw new IndexOutOfBoundsException();
}
Node current = this.head.next;
int i = 0;
while (i++ < index) {
current = current.next;
// 인덱스에 도달할 때까지0에서 부터 current index 값 계속 갱신
}
return current.data;
} // index 값에 도달했을 때 data 반환
@Override
public int indexOf(T t) {
Node current = this.head.next;
int index = 0;
while (current != null) {
if (current.data != null && current.data.equals(t)) {
// null 이 아니면서 데이터가 일치하는지 계속 검사
return index;
// 맞을 경우 index 반환
}
current = current.next;
index++;
}
return -1;
}
@Override
public boolean isEmpty() {
return this.head.next == null;
// head 뒤에 값이 null 값인지만 찾으면 됨
}
@Override
public boolean contains(T t) {
Node current = this.head.next;
// head 는 비어있으므로 current 값은 head.next
while (current != null) {
// null 값이 아닐 경우 계속 진행
if (current.data != null && current.data.equals(t)) {
return true;
}
current = current.next;
// 위에 조건문에서 통과가 안되었을 경우
// current 값을 next 값으로 갱신
}
return false;
}
@Override
public int size() {
return this.size;
// 처음부터 찾으며 시간복잡도가 O(N)이기 때문에
// 그냥 size 값을 가져오면 됨
}
private class Node {
//생성자 노드 초기화 작업
T data;
Node next;
// 다음 노드를 가리키는 포인터
Node(T data) {
this.data = data;
// 생성자
}
Node(T data, Node next) {
this.data = data;
this.next = next;
//생성자 + next도 초기화 필요할 경우 알아서 되도록
}
}
}
DoubleLinkedList
구조
그림정리
- 기본구조
- 위와 같이 DoubleLinkedList 는 포인터가 next, prev 2개임
- prev 라는 또 다른 공간을 만들어주기 때문에 공간을 더 차지함
- 위 그림과 마찬가지로 DoubleLinkedList 에서도 더미 노드를 갖고 있으며 head 와 tail은 값이 없음
- 데이터 추가
- 단순 추가
- 중간에 데이터를 추가해주는 상황이 아니라 단순 데이터 추가라면 가장 끝 tail의 앞에다 데이터를 넣으면 끝이므로 시간 복잡도는 O(1)
- 중간 삽입
- 이전 singleLinkedList와 동일하지만 prev가 새로 생겼으므로 이부분만 잘 연결해주면 된다.
- 1, 2, 3 이라는 데이터가 있고 1과 2 사이에 5라는 데이터를 넣는다고 가정하면 1은 5를바라보고 5의 prev는 1을 next는 2를. 2의 prev은 5로 연결하면 된다.
- 단순 추가
- 검색 by, index
- 배열 같은 경우 index를 통해 한 번에 접근이 가능, singleLinkedList는 head에서 차례로 타고 들어감, DoubleLinkedList도 마찬가지이지만 차이점이 있다.
- tail이 존재하므로 거꾸로도 데이터를 갖고 올 수 있음 따라서 절반으로 나눠서 가까운 쪽에서 데이터를 갖고 올 수 있다.
- 시간복잡도는 O(N/2) 일꺼 같지만 상수항 1/2는 없는 취급하기 떄문에 그냥 O(N)이다. -> 시간복잡도는 single과 같지만 실제로는 1/2 로 알고 있으면 된다.
- 삭제 by, index
- prev -> curr -> next 이렇게 3개의 노드가 있을 때 prev는 next를 next는 prev로 연결시켜주면 끝
코드로 구현해보기
package list;
public class MyDoubleLinkedList<T> implements IList<T> {
private Node head;
private Node tail;
private int size;
public MyDoubleLinkedList() {
this.size = 0;
this.head = new Node(null);
this.tail = new Node(null);
this.head.next = this.tail;
this.tail.prev = this.head;
// size()
// clear() // add()
}
@Override
public void add(T t) {
Node last = this.tail.prev;
// double은 끝에 tail이 있으므로 그 앞에다가 데이터 넣어주면 됨
// tail 앞에 last 라는 노드를 생성해줌
Node newNode = new Node(t, last, tail);
// newNode는 데이터 t를 갖고 있으며 newNode의 next는 tail과 연결
// newNode의 prev은 last -> last는 tail 바로 앞에 있는 node
// head, 1, 2, 3, tail 이 있다고 치면
// 2, last(원래 3의 값), tail
// 2, last(3), newNode, tail
last.next = newNode;
// last의 next 값을 newNode에 연결
this.tail.prev = newNode;
// 원래 있던 tail 앞에 newNode와 연결
this.size++;
// 데이터가 1개 늘어났으니 size도 1업
// 그 다음 get(index)
}
@Override
public void insert(int index, T t) {
if (index > this.size || index < 0) {
throw new IndexOutOfBoundsException();
}
Node prev = null;
Node current = null;
int i = 0;
if (index < this.size / 2) {
// index 값이 전체 사이즈를 2로 나눴을떄 그 값이 index가 더...
// 그냥 index 값이 head와 가까울 때인지 검사
prev = this.head;
// 현재 head 값을 prev에 넣어줌
current = this.head.next;
// head (비어있는 값)의 바로 뒤
// 실질적으로 데이터가 시작되는 부분
while (i++ < index) {
prev = prev.next;
current = current.next;
} // index에 근접할 때 까지 계속 진행
} else {
// index 값이 tail 쪽에 가까울 경우
current = this.tail;
prev = this.tail.prev;
while (i++ < (this.size - index)) {
// 전체 사이즈가 10 index는 8이라고 가정한다면
// 10 -8 = 2번만 실행하면 찾을 수 있음
current = current.prev;
prev = prev.prev;
// 계속 앞으로 찾아감
}
}
Node newNode = new Node(t, prev, current);
// 전체 1부터 10까지 그중에 8과 9사이에 데이터 C를 넣는다고 가정하면
// new node의 prev은 8 next는 current -> 9
current.prev = newNode;
// 9의 앞에 newNode와 연결
prev.next = newNode;
// 8 뒤에 newNode로 연결
this.size++;
// 그 다음 delete by index
}
@Override
public void clear() {
this.size = 0;
// 사이즈 초기화
this.head.next = this.tail;
// head의 next를 tail 로 연결(tail 값은 null 임)
this.head.prev = null;
// head의 prev를 null 값
this.tail.next = null;
// tail 끝을 null 값으로 만듦
this.tail.prev = this.head;
// tail의 앞에 값을 head로 하면 앞 뒤는 모두 null 값
}
@Override
public boolean delete(T t) {
Node prev = this.head;
// 현재 head 값이 prev로 넣어줌 -> Null 값
Node current = prev.next;
// prev의 다음 값을 current -> 데이터 시작점
while (current != null) {
if (current.data.equals(t)) {
// 데이터 값이 t와 같은지 조건 검사
// 조건 통과하면 아래 코드 작동
prev.next = current.next;
// 현재 prev는 1 이라고 가정
// current 는 2라고 가정
// 1,2,3 에서 2를 삭제한다고 가정
// 1의 다음 2의 next -> 3으로 연결
current.next.prev = prev;
// 이게 뭔소리냐 -> current의 next값 (2)의 prev 값에
// prev(1)을 넣어줌
current.next = null;
// current의 next 값을 끊어줌
current.prev = null;
// current의 prev 값을 끊어줌
this.size--;
// current의 값, 데이터를 삭제했으니 사이즈도 줄여줌
return true;
}
// 위 조건식이 진행 안되면 계속 넘어감
prev = prev.next;
current = current.next;
}
return false;
}
@Override
public boolean deleteByIndex(int index) {
if (index >= this.size || index < 0) {
throw new IndexOutOfBoundsException();
}
Node prev = null;
Node current = null;
Node next = null;
int i = 0;
if (index < this.size / 2) {
// index 값이 head와 가까운지 tail에 가까운지 조건 검사
prev = this.head;
current = this.head.next;
while (i++ < index) {
// index값 계속 업데이트하면서 찾아가기
prev = prev.next;
current = current.next;
}
// index 값을 찾은 경우
prev.next = current.next;
// preve 다음 값을 current 다음 값으로 연결
current.next.prev = prev;
// current의 다음 값의 이전값을 prev 와 연결
current.next = null;
current.prev = null;
// current 값의 앞 뒤 끊어주기
} else {
// tail에 가까운 경우의 조건
current = this.tail.prev;
// current는 tail의 앞에 값
next = this.tail;
// next는 tail 값
while (i++ < (this.size - index - 1)) {
// 전체 사이즈가 10
// index는 7
// 10 - 7 = 3
// i = 0부터 시작
// current 가 실제 데이터가 있는 부분에서 시작되기 때문에 -1 해줌
// 왜냐하면 3까지 가면 tail 0값임
next = next.prev;
current = current.prev;
}
next.prev = current.prev;
current.prev.next = next;
current.next = null;
current.prev = null;
}
this.size--;
return true;
}
@Override
public T get(int index) {
if (index >= this.size || index < 0) {
throw new IndexOutOfBoundsException();
}
int i = 0;
Node current = null;
if (index < this.size / 2) {
// index 값이 head와 가까운지 조건 검사
current = this.head.next;
while (i++ < index) {
current = current.next;
}
} else {
current = this.tail.prev;
while (i++ < (this.size - index - 1)) {
current = current.prev;
}
}
return current.data;
// 그 다음 insert(index)
}
@Override
public int indexOf(T t) {
Node current = this.head.next;
int index = 0;
// index는 0부터 차례대로 검색 진행
while (current != null) {
if (current.data != null && current.data.equals(t)) {
// data가 null이 아니고 t와 같을 경우 index 반환
return index;
}
// 위 조건식이 안 맞을경우 다음 index로 넘어감
current = current.next;
index++;
}
return -1;
}
@Override
public boolean isEmpty() {
return this.head.next == this.tail;
// head 값은 null 값 -> head next 값을 null 값 tail로 연결
}
@Override
public boolean contains(T t) {
Node current = this.head.next;
while (current != null) {
if (current.data != null && current.data.equals(t)) {
return true;
}
// 위 조건이 성립 안될 경우 계속 다음 current로 진행
current = current.next;
}
return false;
}
@Override
public int size() {
return this.size;
}
private class Node {
T data;
Node prev;
Node next;
Node(T data) {
this.data = data;
}
Node(T data, Node prev, Node next) {
this.data = data;
this.prev = prev;
this.next = next;
}
}
}
출처 : https://opentutorials.org/module/1335/8821 , 패캠, https://visualgo.net/en, https://opentutorials.org/module/1335/8821, https://opentutorials.org/module/1335/8857
댓글남기기