ArrayList
의 단점
- 배열은 필요한 배열의 크기를 미리 확보하기때문에 나머지 공간은 사용되지 않고 낭비된다
- 데이터의 추가와 삭제가 어려우며 이로인해 성능이 좋지않다
낭비되는 메모리 없이 필요한만큼의 메모리만 사용하고 데이터를 중간에 추가하거나 삭제할 때도 효율적인 자료구조가 바로 노드와 연결
이다노드와 연결
의 '노드'는 내부에 저장할 데이터인 item과 다음으로 '연결'할 노드의 참조인 next를 가지고 있다.
Node
클래스
public class Node {
Object item;
Node next;
public Node(Object item) {
this.item = item;
}
@Override
public String toString() {
StringBuilder sb = new StringBuilder();
Node x = this;
sb.append("[");
while (x != null) { // x가 null일 때까지 반복
sb.append(x.item);
if (x.next != null) {
sb.append("->");
}
x = x.next; //다음 노드의 참조값
}
sb.append("]");
return sb.toString();
}
//return item + "->" + next.item + "->" + next.next.item;
}
Node
클래스 내부에는 데이터를 저장하기위한 item
필드와 그 다음 노드의 참조값을 가지고 있는 next
필드로 이루어져있다.
따라서 하나의 Node
에는 하나의 데이터를 저장할 수 있으며 이러한 노드가 next
의 참조값으로 연결되어 있는 것을 LinkedList
라고한다.
여기서에서 정의한 toString
메서드는 노드의 구조를 출력할 때 item->item2->item3->..의 구조로 출력하기위해 임의로 작성한 메서드이다.
LinkedList의 메서드
LinkedList필드
private Node<E> first;
private int size = 0;
LinkedList
의 필드로는 하나의 노드를 의미하는 first
필드와 현재 얼만큼의 Node
가 들어왔는지를 의미하는 size
필드로 나뉜다.first
필드는 노드의 시작점으로 검색,조회,삭제 등의 메서드에서 메서드에 맞는 역할을 수행하기위해서 Node의 시작점인 first
를 참조해야한다.
실제 자바에서 제공하는 LinkedList
에는 이중 연결리스트를 지원하여 마지막 노드를 의미하는 last
필드도 선언되어있다.
add(E e)
public void add(E e) {
Node<E> newNode = new Node<>(e);
if (first == null) {
first = newNode;
} else{
Node<E> lastNode = getLastNode();
lastNode.next = newNode;
}
size++;
}
private Node<E> getLastNode() {
Node<E> x = first;
while (x.next != null) {
x = x.next;
}
return x;
}
먼저 데이터를 저장하기위한 메서드로 새로운 데이터를 저장할 newNode
를 생성하고 이 데이터가 LinkedList
의 첫 노드일수도있기때문에 first
가 null
일경우 newNode
를 first
변수로 넣어준다.
만약 첫 노드가 아닐경우 노드를 순회하며 마지막 노드를 가져온 뒤 마지막 노드의 next
필드에 새로운 데이터를 가지고있는 newNode
를 참조해준다.
그리고나서 노드의 수를 의미하는 size필드를 +1해준다.
getLastNode()
메서드는 first
필드로부터 첫 노드를 가져온 뒤에 first.next
를 모두 순회하며 마지막 노드를 리턴받는다.
add(E e, int index)
public void add(E e, int index) {
Node<E> newNode = new Node<>(e);
if (index == 0) {
newNode.next = first;
first = newNode;
}else{
Node<E> prev = getNode(index-1);
newNode.next = prev.next;
prev.next = newNode;
}
size++;
}
원하는 인덱스에 새로운 데이터를 갖는 노드를 추가하는 메서드이다
- 맨 앞에 추가
- 그 외에 추가
두 가지를 if문으로 분기를 나눈다
만약 맨 앞에 추가를 의미하는 0을 매개변수로 받았을 경우에는 아래와 같은 그림구조가 나온다.
![[Pasted image 20240608194542.png]]
새로운 newNode
의 next
필드에 기존에 0인덱스를 가지고있던 first
필드를 넣어주고
새로운 노드는 0인덱스이므로 맨 처음을 의미한다. 따라서 newNode
를 first
변수가 참조할 수 있도록 변경해준다.
그리고 0인덱스가 아닌 다른인덱스에 들어올 경우에는 아래와 같은 그림이나온다.
![[Pasted image 20240608195256.png]]
먼저 인덱스 매개변수가 1로 들어왔기 때문에 기존의 인덱스 0과 1. 즉, A노드와 B노드 사이에 공간을 만들어야한다.getNode
메서드를 통해서 index-1
의 노드 (추가하고자하는 노드의 이전 노드)를 가져와 prev
변수로 선언해준다
그리고나서 newNode
의 next
필드에는 B노드의 참조값이 들어와야한다. B의 참조값은 기존에 prev
노드의 next
필드에 들어있으므로 newNode.next = prev.next
로 참조해준다.
그 다음에는 prev
가 newNode
를 참조하도록 연결해주면된다.prev.next = newNode;
그리고 최종적으로 데이터가 새로 들어왔으므로 size+1을 해준다
remove(int index)
public E remove(int index) {
Node<E> removeNode = getNode(index);
E removedItem = removeNode.item;
if (index == 0) {
first = removeNode.next;
}else{
Node<E> prev = getNode(index - 1);
prev.next = removeNode.next;
}
removeNode.next = null;
removeNode.item = null;
size--;
return removedItem;
}
삭제하는 메서드도 add메서드와 동일하지만 데이터가 삭제되기때문에 size를 -1해주어야하고 삭제될 대상의 next
필드와 item
필드를 null
값을 준다.removeNode
는 참조하는 변수가 없으므로 GC에의해 제거된다.
이외의 메서드들은 add와 메커니즘자체는 비슷하기때문에 설명을 생략한다.
set(E e, int index)
public E set(E e, int index) {
Node<E> x = getNode(index);
E oldValue = x.item;
x.item = e;
return oldValue;
}
indexOf(E e)
public int indexOf(E e) {
int index = 0;
for (Node<E> x = first; x != null; x = x.next) {
if (x.item.equals(e)) {
return index;
}
index++;
}
return -1;
}
private Node<E> getLastNode() {
Node<E> x = first;
while (x.next != null) {
x = x.next;
}
return x;
}
public Node<E> getNode(int index) {
Node<E> x = first;
for (int i = 0; i < index; i++) {
x = x.next;
}
return x;
}
public E get(int index) {
Node<E> x = getNode(index);
return x.item;
}
public int getSize() {
return size;
}
전체 코드
package mid2.collection.link;
public class MyLinkedListV3<E> {
private Node<E> first;
private int size = 0;
//새로운 노드를 만드는 메서드
public void add(E e) {
Node<E> newNode = new Node<>(e);
if (first == null) {
first = newNode;
} else{
Node<E> lastNode = getLastNode();
lastNode.next = newNode;
}
size++;
}
public void add(E e, int index) {
Node<E> newNode = new Node<>(e);
if (index == 0) {
newNode.next = first;
first = newNode;
}else{
Node<E> prev = getNode(index-1);
newNode.next = prev.next;
prev.next = newNode;
}
size++;
}
public E remove(int index) {
Node<E> removeNode = getNode(index);
E removedItem = removeNode.item;
if (index == 0) {
first = removeNode.next;
}else{
Node<E> prev = getNode(index - 1);
prev.next = removeNode.next;
}
removeNode.next = null;
removeNode.item = null;
size--;
return removedItem;
}
public E set(E e, int index) {
Node<E> x = getNode(index);
E oldValue = x.item;
x.item = e;
return oldValue;
}
public int indexOf(E e) {
int index = 0;
for (Node<E> x = first; x != null; x = x.next) {
if (x.item.equals(e)) {
return index;
}
index++;
}
return -1;
}
private Node<E> getLastNode() {
Node<E> x = first;
while (x.next != null) {
x = x.next;
}
return x;
}
public Node<E> getNode(int index) {
Node<E> x = first;
for (int i = 0; i < index; i++) {
x = x.next;
}
return x;
}
public E get(int index) {
Node<E> x = getNode(index);
return x.item;
}
public int getSize() {
return size;
}
@Override
public String toString() {
return "MyLinkedListV1{" + "first=" + first + ", size=" + size + '}';
}
private static class Node<E>{
E item;
Node<E> next;
public Node(E item) {
this.item = item;
}
@Override
public String toString() {
StringBuilder sb = new StringBuilder();
Node<E> x = this;
sb.append("[");
while (x != null) { // x가 null일 때까지 반복
sb.append(x.item);
if (x.next != null) {
sb.append("->");
}
x = x.next; //다음 노드의 참조값
}
sb.append("]");
return sb.toString();
}
}
}
여기서 Node클래스가 내부클래스로 선언되어있는데 Node클래스는 LinkedList
클래스에서만 사용되지 외부에서 사용될 일은 없기때문에 Node
클래스는 LinkedList
의 내부클래스로 들어와도 문제가 없다. 캡슐화를 극대화할 수 있다.
실무에서는 연결리스트보다는 배열리스트가 자주 사용된다고한다.
연결리스트를 사용하는 케이스는 무수히 많은 데이터(대략 10만건이상)를 앞에 추가, 뒤에 추가하고자하는 경우에 사용된다. 이외에 경우에는 연결리스트를 사용한다
그 이유는 ArrayList vs LinkedList에서 알아본다.
공부자료 참조: 인프런 - 김영한
https://www.inflearn.com/users/74366/@yh
'Language > Java' 카테고리의 다른 글
[Java - 자료구조] Set인터페이스 (0) | 2024.06.12 |
---|---|
[JAVA - 자료구조] ArrayList vs LinkedList (1) | 2024.06.09 |
[JAVA] 익명 클래스 (1) | 2024.06.09 |
[JAVA] 날짜와 시간 - LocalDate, LocalTime (0) | 2024.06.09 |
[JAVA - 자료구조] ArrayList (1) | 2024.06.07 |
포스팅이 좋았다면 "좋아요❤️" 또는 "구독👍🏻" 해주세요!