study/Java
LinkedList
으녕오리
2025. 4. 4. 10:24
노드와 연결
배열 리스트의 단점
배열 리스트는 내부에 배열을 사용해서 데이터를 보관하고 관리한다.
배열은 필요한 배열의 크기를 미리 확보해야 한다. -> 공간 낭비 발생
앞이나 중간에 데이터를 추가하거나 삭제하는 경우 -> 데이터를 이동으로 인한 성능 저하 발생
노드와 연결(노드를 만들고 각 노드를 서로 연결)
낭비되는 메모리 x, 앞이나 중간에 데이터를 추가, 삭제할 때 효율적
- 노드에 데이터 추가
코드 구현
더보기
public class Node {
Object item;
Node next;
public Node(Object item) {
this.item = item;
}
}- 모든 노드 탐색하기
더보기
Node x = first;
while (x != null) {
System.out.println(x.item);
x = x.next;
}- toString()을 직접 구현
더보기
public class Node {
Object item;
Node next;
public Node(Object item) {
this.item = item;
}
}
public class Node {
Object item;
Node next;
public Node(Object item) {
this.item = item;
}
/*
//IDE 생성 toString()
@Override
public String toString() {
return "Node{" +
"item=" + item +
", next=" + next +
'}';
}
*/
@Override
public String toString() {
StringBuilder sb = new StringBuilder();
Node x = this;
sb.append("[");
while (x != null) {
sb.append(x.item);
if (x.next != null) {
sb.append("->");
}
x = x.next;
}
sb.append("]");
return sb.toString();
}
}- 노드와 연결을 활용한 다양한 기능
- 모든 노드 탐색
- 마지막 노드 조회
- 특정 index의 노드 조회
- 노드에 데이터 추가
더보기
public class MyLinkedListV1 {
private Node first;
private int size = 0;
public void add(Object e) {
Node newNode = new Node(e);
if (first == null) {
first = newNode;
} else {
Node lastNode = getLastNode();
lastNode.next = newNode;
}
size++;
}
private Node getLastNode() {
Node x = first;
while (x.next != null) {
x = x.next;
}
return x;
}
public Object set(int index, Object element) {
Node x = getNode(index);
Object oldValue = x.item;
x.item = element;
return oldValue;
}
public Object get(int index) {
Node node = getNode(index);
return node.item;
}
private Node getNode(int index) {
Node x = first;
for (int i = 0; i < index; i++) {
x = x.next;
}
return x;
}
public int indexOf(Object o) {
int index = 0;
for (Node x = first; x != null; x = x.next) {
if (o.equals(x.item))
return index;
index++;
}
return -1;
}
public int size() {
return size;
}
@Override
public String toString() {
return "MyLinkedListV1{" +
"first=" + first +
", size=" + size +
'}';
}
}- 정리
- 노드는 내부에 데이터와 다음 노드에 대한 참조를 가지고 있다.
- next 필드를 통해 참조값을 보관 -> 메모리 낭비가 발생하긴 한다.
- 노드를 연결해서 사용하는 자료 구조로 리스트를 만듦 -> 연결 리스트
연결 리스트1 - 시작
- 리스트(순서 O, 중복 O)의 내부에서
- 배열을 사용 -> ArrayList
- 노드와 연결 구조를 사용 -> LinkedLlist
연결 리스트와 빅오
더보기
public class MyLinkedListV1 {
private Node first;
private int size = 0;
public void add(Object e) {
Node newNode = new Node(e);
if (first == null) {
first = newNode;
} else {
Node lastNode = getLastNode();
lastNode.next = newNode;
}
size++;
}
private Node getLastNode() {
Node x = first;
while (x.next != null) {
x = x.next;
}
return x;
}
public Object set(int index, Object element) {
Node x = getNode(index);
Object oldValue = x.item;
x.item = element;
return oldValue;
}
public Object get(int index) {
Node node = getNode(index);
return node.item;
}
private Node getNode(int index) {
Node x = first;
for (int i = 0; i < index; i++) {
x = x.next;
}
return x;
}
public int indexOf(Object o) {
int index = 0;
for (Node x = first; x != null; x = x.next) {
if (o.equals(x.item))
return index;
index++;
}
return -1;
}
public int size() {
return size;
}
@Override
public String toString() {
return "MyLinkedListV1{" +
"first=" + first +
", size=" + size +
'}';
}
}
- Object get(int index)
- 특정 위치에 있는 데이터를 반환
- O(n) -> 특정 위치 찾기
- void add(Object e)
- 마지막에 데이터 추가
- O(n) -> 마지막 노드 찾기
- Object set(int index, Object element)
- 특정 위치의 데이터를 찾아서 변경 후 기존 값 반환
- O(n) -> 특정 위치 찾기
- int indexOf(Object o)
- 데이터를 검색 후 검색된 위치 반환
- O(n) -> 모든 노드 순회
연결 리스트2 - 특정 위치에 데이터를 추가, 삭제
- 첫번째 위치의 데이터 추가, 삭제 -> O(1)
| 배열 | 리스트 | |
| index | 실제 index가 존재 | 존재x, 가정일 뿐이고 연결된 순서를 뜻한다. |
| 이동 여부 | O(모든 데이터를 하나씩 이동) | X(새로 생성한 노드의 참조만 변경) |
- 특정 위치에 데이터 추가 -> O(n)
- 새로운 노드를 생성하고, 노드가 입력될 위치의 직전 노드(prev) 찾기
- 신규 노드와 다음 노드를 연결, 직전 노드(prev)의 다음 노드를 연결
- 직전 노드(prev)에 신규 노드를 연결
- 특정 위치의 데이터 삭제 -> O(n)
- 삭제 대상을 찾고 삭제 대상의 직전 노드(prev) 찾기
- 직전 노드(prev)의 다음 노드를 삭제 후 노드의 다음 노드와 연결
- 삭제 노드의 데이터를 초기화
- 코드 구현
더보기
public class MyLinkedListV2 {
private Node first;
private int size = 0;
public void add(Object e) {
Node newNode = new Node(e);
if (first == null) {
first = newNode;
} else {
Node lastNode = getLastNode();
lastNode.next = newNode;
}
size++;
}
private Node getLastNode() {
Node x = first;
while (x.next != null) {
x = x.next;
}
return x;
}
//추가 코드
public void add(int index, Object e) {
Node newNode = new Node(e);
if (index == 0) {
newNode.next = first;
first = newNode;
} else {
Node prev = getNode(index - 1);
newNode.next = prev.next;
prev.next = newNode;
}
size++;
}
public Object set(int index, Object element) {
Node x = getNode(index);
Object oldValue = x.item;
x.item = element;
return oldValue;
}
//추가 코드
public Object remove(int index) {
Node removeNode = getNode(index);
Object removedItem = removeNode.item;
if (index == 0) {
first = removeNode.next;
} else {
Node prev = getNode(index - 1);
prev.next = removeNode.next;
}
removeNode.item = null;
removeNode.next = null;
size--;
return removedItem;
}
public Object get(int index) {
Node node = getNode(index);
return node.item;
}
private Node getNode(int index) {
Node x = first;
for (int i = 0; i < index; i++) {
x = x.next;
}
return x;
}
public int indexOf(Object o) {
int index = 0;
for (Node x = first; x != null; x = x.next) {
if (o.equals(x.item))
return index;
index++;
}
return -1;
}
public int size() {
return size;
}
@Override
public String toString() {
return "MyLinkedListV2{" +
"first=" + first +
", size=" + size +
'}';
}
}- 성능 비교표
데이터를 조회할 일이 많다, 뒷 부분에 데이터 추가 -> 배열 리스트
앞쪽에 데이터 추가, 삭제 -> 연결 리스트
- 이중 연결 리스트
- 성능을 더 개선할 수 있다.
- 자바가 제공하는 연결 리스트는 이중 연결 리스트이다.
- 마지막 노드를 참조하는 변수를 가지고 있다. -> 뒤에 추가, 삭제 : O(1)
연결 리스트3 - 제네릭 도입
제네릭을 도입하면 타입 안전성이 보장된 자료 구조를 만들 수 있다.
Node는 연결 리스트 내부에서만 사용되므로 중첩 클래스로 만든다.
코드 구현
더보기
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++;
}
private Node<E> getLastNode() {
Node<E> x = first;
while (x.next != null) {
x = x.next;
}
return x;
}
public void add(int index, E e) {
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 set(int index, E element) {
Node<E> x = getNode(index);
E oldValue = x.item;
x.item = element;
return oldValue;
}
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.item = null;
removeNode.next = null;
size--;
return removedItem;
}
public E get(int index) {
Node<E> node = getNode(index);
return node.item;
}
private Node<E> getNode(int index) {
Node<E> x = first;
for (int i = 0; i < index; i++) {
x = x.next;
}
return x;
}
public int indexOf(E o) {
int index = 0;
for (Node<E> x = first; x != null; x = x.next) {
if (o.equals(x.item))
return index;
index++;
}
return -1;
}
public int size() {
return size;
}
@Override
public String toString() {
return "MyLinkedListV3{" +
"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> temp = this;
sb.append("[");
while (temp != null) {
sb.append(temp.item);
if (temp.next != null) {
sb.append("->");
}
temp = temp.next;
}
sb.append("]");
return sb.toString();
}
}
}