[JAVA - 자료구조] LinkedList
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