나만의 LinkedList 만들어보기
LinkedList 만들기
LinkedList란
ArrayList 는 삽입과 삭제를 수행할 때 연속적인 특징을 깨뜨리지 않기 위해 배열을 Shift 해줘야 합니다.
이 때 발생하는 시간복잡도는 O(n) 입니다.
그러나 LinkedLIst를 이용하게 되면, 시간복잡도를 O(1)만으로 끝낼 수 있기 때문에,
ArrayLIst에 비해 삽입과 삭제가 월등히 빠르다고 할 수 있습니다.
구조
LinkedList의 구조는 다음과 같습니다.
LinkedList는 내부적으로 Node라는 객체를 갖고 있습니다.
이 Node들을 서로 연결해서 자료를 참조하는 방법 입니다.
Node의 next 변수는 자기자신의 다음으로 올 Node객체를 알고 있습니다.
그러나 LinkedList 역시 문제가 있습니다.
ArrayList는 논리적 저장순서와 물리적 저장 순서가 일치하기 때문에 원하는 index 번호를 알면
O(1)의 시간으로 해당 자료에 바로 참조 할 수 있습니다.
그러나 LinkedLIst는 원하는 자료를 찾기 위해서는 처음 Node부터 검색해봐야 하기 때문에
O(n)의 시간만큼 걸립니다.
구현하기
클래스이름은 MyLinkedList로 하겠습니다.
클래스를 하나 만들고 제너릭 타입을 선언해주세요.
public class MySinglyLinkedList<E> {
}
Node 클래스를 내부에 하나 만들어주세요.
private class Node {
// 값을 저장할 때 쓰일 변수
Object data;
// 다음 노드를 가르킬 변수
Node next;
// 처음 LinkedList를 만들때 쓰일 생성자
public Node(Object data) {
this.data = data;
this.next = null;
}
}
LinkedList는 Node가 몇개 있는지 알려주는 size 변수와
첫번째 노드를 가르킬 head 변수가 필요합니다.
private int size;
private Node head;
지금까지의 작업
public class MySinglyLinkedList<E> {
private class Node {
Object data;
Node next;
// 처음 LinkedList를 만들때 쓰일 생성자
public Node(Object data) {
this.data = data;
this.next = null;
}
}
private int size;
private Node head;
//LinkedList의 생성자
//처음 LinkedList를 만든다면 head는 비어 있다.
public MySinglyLinkedList() {
head = null;
size = 0;
}
add함수 만들기
public boolean add(E element) {
// 첫번 째 노드이면,
if(head == null) {
head = new Node(element);
} else {
// 첫번째 노드부터 탐색
Node node = head;
// 헤더의 다음 노드를 계속 탐색하는데, 다음 노드가 null이 아닐 떄 까지 탐색한다.
for( ; node.next != null; node = node.next) {
}
// 탐색을 다했으면 node 객체가 마지막 노드를 가지고 있게 된다.
node.next = new Node(element);
}
size++;
return true;
}
add() 함수는 마지막 Node를 찾아 새로운 Node를 만들어 이어줘야 합니다.
그러기 위해서는 처음 Node부터 Node.next가 null 을 만날 때 까지 탐색을 해야합니다.
탐색한 노드를 node 변수에 담고, node.next에 새로운 Node객체를 생성해주면 됩니다.
get함수 만들기
// 몇번째 노드를 가져오고 싶은지
public E get(int index) {
if(index < 0 || size <=index)
throw new IndexOutOfBoundsException();
Node node = getNode(index);
return (E) node.data;
}
public Node getNode(int index) {
Node node = head;
// index 까지 node를 움직인다.
for(int i=0; i<index; i++) {
node = node.next;
}
return node;
}
get() 함수는 해당 index 값 까지 node를 head부터 돌려서 해당 Node객체를 가져오면 됩니다.
이때 index의 값이 마이너스 값이거나 size보다 같거나크면 예외를 던져줍니다.
set함수 만들기
// n번째 있는 노드의 값 수정하고
// 원래 들어있던 값 리턴하기
public E set(int index,E element ) {
//get() 호출하기
E old = get(index);
// 커서를 head에 맞춘다.
Node node = head;
// index까지 node를 움직인다.
for(int i=0; i<index; i++) {
node= node.next;
}
// node
node.data = element;
return old;
}
set() 함수는 방금만든 get() 함수와 비슷합니다.
get() 함수처럼 index 만큼 for문을 돌려 해당 Node객체를 가르키고
가르킨 객체의 data를 변경해주면 됩니다.
indexOf함수 만들기
// 해당 요소가 몇번 째 노드에 있는지?
public int indexOf(E element) {
Node node = head;
int cnt =0;
for(; node.next != null; node=node.next) {
if(node.data.equals(element)) {
return cnt;
}
cnt++;
}
return -1;
}
indexOf() 함수는 Node 객체에 해당 값이 존재하는지 판별하는 객체입니다.
for문을 돌때마다 Node의 data에 접근하여 equals 함수로 비교를 해줍니다.
remove 함수
//해당 index의 요소 삭제 중요!
public E remove(int index) {
E element = get(index);
Node preNode = getNode(index - 1);
// 첫번째 노드이면?
if (index == 0) {
head = new Node(head.next);
} else {
preNode.next = preNode.next.next;
}
size--;
return element;
}
remove() 함수는 조금 복잡합니다.
1) 첫번째 노드를 삭제한다면 첫번 째 노드의 다음 노드가 head가 됩니다.
2) 중간에 노드를 삭제한다면, 이전 노드와 다음 노드를 서로 이어줘야 합니다.
코드
마무리
| 구분 | LinkedList |
|---|---|
| add(끝) | n |
| add(시작) | 1 |
| add(일반적으로) | n |
| get/set | n |
| indexOf | n |
| remove(끝) | n |
| remove(시작) | 1 |
| remove(일반적으로) | n |
지금까지 단방향 LinkedLIst를 구현해보았습니다.
다음시간에는 더 많은 장점을 가진 양방향 LinkedList로 찾아뵙겠습니다.