노드와 연결1
배열 리스트의 단점 : 배열 리스트는 내부에 배열을 사용해서 데이터를 보관하고 관리한다. 이로 인해 다음과 같은 단점을 가진다
1. 배열의 사용하지 않는 공간 낭비
-배열은 필요한 배열의 크기를 미리 확보해야 한다. 데이터가 얼마나 추가될지 예측할 수 없는 경우 나머지 공간은 사용되지 않고 낭비된다.
2. 배열의 중간 데이터 추가
- 앞이나 중간에 데이터를 추가하거나 삭제하는 경우 많은 데이터를 이동해야 하기 때문에 성능이 좋지 않다.
노드와 연결
노드와 연결 구조를 사용하면 이 문제를 해결할 수 있다.
낭비되는 메모리 없이 딱 필요한 만큼만 메모리를 확보해서 사용하고, 또 앞이나 중간에 데이터를 추가하거나 삭제할 때도 효율적인 자료구조이다. 노드를 만들고 각 노드를 서로 연결하는 방식이다.
public class Node{
Object item;
Node next;
}
노드 클래스는 내부에 저장할 데이터인 item과, 다음으로 연결할 노드의 참조인 next를 가진다.
이 노드를 사용해서 데이터 A, B, C를 연결해보자.
1. Node0 인스턴스의 next필드에 새로 만든 노드의 참조값을 넣어준다.
2. 이렇게 하면 첫번째 두번째 노드가 연결된다.
3. 첫번째 노드의 node.next를 호출하면 두번째 노드를 구할 수 있다.
4. Node1 인스턴스의 next필드에 새로만든 노드의 참조값을 넣어준다.
5. 이렇게 하면 두번째와 세번째 노드가 연결된다.
6. 첫번째 노드의 node.next.next를 호출하면 세번째 노드를 구할 수 있다.
public class NodeMain1 {
public static void main(String[] args) {
//노드 생성하고 연결하기 : A -> B -> C
Node first = new Node("A");
first.next = new Node("B");
first.next.next = new Node("C");
System.out.println("모든 노드 탐색하기");
System.out.println("first.item = " + first.item);
System.out.println("first.next.item = " + first.next.item);
System.out.println("first.next.next.item = " + first.next.next.item);
System.out.println("모든 노드 탐색하기");
Node x = first;
while (x != null){
System.out.println("x.item");
x = x.next
}
}
}
노드와 연결2
toString() - IDE
노드의 연결 상태를 더 편하게 보기 위해 toString()을 오버라이딩 해보자.
public class Node {
Object item;
Node next;
public Node(Object item) {
this.item = item;
}
@Override
public String toString() {
return "Node{" +
"item=" + item +
", next=" + next +
'}';
}
}public class NodeMain2 {
public static void main(String[] args) {
Node first = new Node("A");
first.next = new Node("B");
first.next.next = new Node("C");
System.out.println("연결된 노드 출력하기");
System.out.println(first);
}
}연결된 노드 출력하기
Node{item=A, next=Node{item=B, next=Node{item=C, next=null}}}
괄호가 여러개 쳐져있고 문제가 있는 것을 알 수 있다.
그 이유는 A B C 모두 노드이기 때문에 발생하는 문제이다.
x001, x002 x003이라고 가정했을때 셋 다 노드이기에 출력시에 오버라이딩 된 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();
}연결된 노드 출력하기
[A->B->C]
[B->C]
노드와 연결3
노드와 연결을 활용해서 다음과 같은 여러 기능들을 만들어보자
1. 모든 노드 탐색하기
2. 마지막 노드 조회하기
3. 특정 index의 노드 조회하기
4. 노드에 데이터 추가하기
public class NodeMain3 {
public static void main(String[] args) {
Node first = new Node("A");
first.next = new Node("B");
first.next.next = new Node("C");
System.out.println(first);
//모든 노드 탐색하기
System.out.println("모든 노드 탐색하기");
printAll(first);
//마지막 노드 조회하기
Node lastNode = getLastNode(first);
System.out.println("lastNode = " + lastNode);
//특정 index의 노드 조회하기
int index = 2;
Node index2Node = getNode(first, index);
System.out.println("index2Node = " + index2Node.item);
System.out.println("데이터 추가하기");
add(first, "D");
System.out.println(first);
add(first, "E");
System.out.println(first);
add(first, "F");
System.out.println(first);
}
private static Node getNode(Node node, int index) {
Node x = node;
for(int i = 0; i < index; i++){
x = x.next;
}
return x;
}
private static void printAll(Node node) {
Node x = node;
while (x != null){
System.out.println(x.item);
x = x.next;
}
}
private static Node getLastNode(Node node) {
Node x = node;
while (x.next != null){
x = x.next;
}
return x; //x.next == null
}
private static void add(Node node, String param) {
Node lastNode = getLastNode(node);
lastNode.next = new Node(param);
}
}
[A->B->C]
모든 노드 탐색하기
A
B
C
lastNode = [C]
index2Node = C
데이터 추가하기
[A->B->C->D]
[A->B->C->D->e]
[A->B->C->D->e->F]
모든 노드 탐색하기
printAll(Node node) : 다음 노드가 없을 때 까지 반복해서 노드의 데이터를 출력한다
마지막 노드 조회하기
Node getLastNode(Node node) : 마지막 노드를 조회한다.
Node.next 의 참조값이 null이면 노드의 끝이다.
getLastNode()는 노드를 순서대로 탐색하면서 Node.next의 참조값이 null 인 노드를 찾아서 반환한다.
여기서는 마지막에 있는 C 값을 가지고 있는 노드가 출력된다.
특정 index의 노드 조회하기
getNode(Node node, int index) : index로 특정 위치의 노드를 찾는다
x = x.next 를 호출할 떄마다 x가 참조하는 노드의 위치가 순서대로 하나씩 증가한다
index의 수 만큼만 반복해서 이동하면 원하는 위치의 노드를 찾을 수 있다.
데이터 추가하기
데이터를 추가할때는 새로운 노드를 만들고, 마지막 노드에 새로 만든 노드를 연결하면 된다
정리
-노드는 내부에 데이터와 다음 노드에 대한 참조를 가지고 있다.
-지금까지 설명한 구조는 각각의 노드가 참조를 통해 연결(Link, 링크)되어 있다.
-데이터를 추가할 때 동적으로 필요한 만큼의 노드만 만들어서 연결하면 된다. 따라서 배열과 다르게 메모리를 낭비하지 않는다.
-이렇게 각각의 노드를 연결(링크)해서 사용하는 자료 구조로 리스트를 만들 수 있는데, 이것을 연결 리스트라 한다.
직접 구현하는 연결 리스트1 - 시작
이전에 배열을 통해 리스트를 만들었는데 이것은 배열 리스트(ArrayList)라고 했다.
https://surrealcode.tistory.com/76
자바 컬렉션 프레임워크 - ArrayList
배열의 특징 1- 배열과 인덱스배열과 같이 여러 데이터(자료)를 구조화 해서 다루는 것을 자료 구조라한다.자바는 배열 뿐만 아니라, 컬렉션 프레임워크라는 이름으로 다양한 자료 구조를 제공
surrealcode.tistory.com
이번에는 배열이 아닌 앞서 본 노드와 연결 구조를 통해서 리스트를 만들어보려 한다. 이런 자료 구조를 연결 리스트(LinkedList)라 한다. 참고로 링크드 리스트, 연결 리스트라는 용어를 둘 다 사용한다.
연결 리스트는 배열 리스트의 단점인, 메모리 낭비, 중간 위치의 데이터 추가에 대한 성능 문제를 어느정도 극복할 수 있다.
리스트 자료 구조
순서가 있고, 중복을 허용하는 자료 구조를 리스트(List)라 한다.
우린 앞서 MyArrayList 시리즈를 만들었었다. 배열 리스트도, 연결 리스트도 모두 같은 리스트이다. 리스트의 내부에서 배열을 사용하는가 아니면 노드와 연결 구조를 사용하는가의 차이만 있을 뿐이다.
배열 리스트를 사용하든 연결 리스트를 사용하든 둘 다 리스트 자료 구조이기 때문에 리스트를 사용하는 개발자 입장에서는 거의 비슷하게 느껴져야 한다. 쉽게 이야기해서 리스트를 사용하는 개발자 입장에서 MyArrayList를 사용하든 MyLinkedList를 사용하든 내부가 어떻게 돌아가는지 몰라도, 순서가 있고, 중복을 허용하는 자료구조구나 생각하고 사용할 수 있어야 한다.
연결리스트는 다음과 같다.
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)) {
return index;
}
index++;
}
return -1;
}
public int size(){
return size;
}
@Override
public String toString() {
return "MyLinkedListV1{" +
"first=" + first +
", size=" + size +
'}';
}
}
public class MyLinkedListV1Main {
public static void main(String[] args) {
MyLinkedListV1 list = new MyLinkedListV1();
System.out.println("==데이터 추가==");
System.out.println(list);
list.add("a");
System.out.println(list);
list.add("b");
System.out.println(list);
list.add("c");
System.out.println(list);
System.out.println("==기능 사용==");
System.out.println("list.size() = " + list.size());
System.out.println("list.get(1) = " + list.get(1));
System.out.println("list.indexOf(c) = " + list.indexOf("c"));
System.out.println("list.set(2, 'z') = " + list.set(2, "z"));
System.out.println(list);
System.out.println("==범위 초과==");
list.add("d");
System.out.println(list);
list.add("e");
System.out.println(list);
//범위 초과, capacity가 늘어나지 않으면 예외 발생
list.add("f");
System.out.println(list);
}
}==데이터 추가==
MyLinkedListV1{first=null, size=0}
MyLinkedListV1{first=[a], size=1}
MyLinkedListV1{first=[a->b], size=2}
MyLinkedListV1{first=[a->b->c], size=3}
==기능 사용==
list.size() = 3
list.get(1) = b
list.indexOf(c) = 2
list.set(2, "z") = c
MyLinkedListV1{first=[a->b->z], size=3}
==범위 초과==
MyLinkedListV1{first=[a->b->z->d], size=4}
MyLinkedListV1{first=[a->b->z->d->e], size=5}
MyLinkedListV1{first=[a->b->z->d->e->f], size=6}
MyArrayListV1Main 코드를 거의 그대로 사용하였다(동일 PC로 진행한것은 아니기에 Node 구현 부분은 다르다 참고하자)
생성자 부분만 주의해주자
- 기존에 만든 MyArrayListV1 리스트와 제공하는 기능이 같기 때문에 메서드 이름도 같게 맞추어 두었다.
- 연결리스트는 데이터를 추가할 때 마다 동적으로 노드가 늘어다기 때문에 범위를 초과하는 문제는 발생하지 않는다.
연결리스트의 빅오
Object get(int index)
- 특정 위치에 있는 데이터를 반환한다.
- O(n) -> 배열은 인덱스로 원하는 데이터를 즉시 찾을 수 있지만 연결 리스트에서 사용하는 노드들은 배열이 아니다. 단지 다음 노드에 대한 참조가 있을 뿐이다. 따라서 인덱스로 원하는 위치의 데이터를 찾으려면 O(n)이 걸린다
void Add(Object e)
- 마지막에 데이터를 추가한다.
- O(n) -> 마지막 노드를 찾는데 O(n)이 소요된다. 마지막 노드에 새로운 노드를 추가하는데 O(1)이 걸린다. 따라서 O(n)이다.
Object set(int index, Object element)
- 특정 위치에 있는 데이터를 찾아서 변경한다. 그리고 기존 값을 반환한다.
- O(n) -> 특정 위치의 노드를 찾는데 O(n)이 걸린다.
int indexOf(Object o)
- 데이터를 검색하고, 검색된 위치를 반환한다.
- O(n) -> 모든 노드를 순회하면서 equals()를 사용해서 같은 데이터가 있는지 찾는다.
연결리스트를 통해 데이터를 추가하는 방식은 꼭 필요한 메모리만 사용한다. 따라서 배열 리스트의 단점인 메모리 낭비를 해결할 수 있다.
배열 리스트는 중간에 데이터를 추가하거나 삭제할 때 기존 데이터를 한칸씩 이동해야 하는 문제가 있었다. 연결 리스트는 이 문제를 어떻게 해결하는지 알아보자.
직접 구현하는 연결 리스트2 - 추가와 삭제1
특정 위치에 있는 데이터를 추가하고, 삭제하는 기능을 만들자
다음 두 기능을 추가하면 된다.
void add(int index,Object e)
-특정 위치에 데이터를 추가한다
-내부에서 노드도 함께 추가된다.
Object remove(int index)
-특정위치에 있는 데이터를 제거한다.
-내부에서 노드도 함께 제거된다.
1. void add(int index, Object e)
-노드를 추가했으므로 오른쪽 노드의 index가 하나씩 뒤로 밀려난다.
연결 리스트는 배열처럼 실제 index가 존재하는 것이 아니다. 연결 리스트에서 index는 연결된 순서를 뜻한다.
-배열의 경우 첫번째 항목에 데이터가 추가되면 모든 데이터를 오른쪽으로 하나씩 밀어야 하지만 연결 리스트는 새로 생성한 노드의 참조만 변경하면 된다. 나머지 노드는 어떤 일이 일어난지도 모른다.
-연결리스트의 첫번째 항목에 값을 추가하는 것은 매우 빠르다 O(1)로 표현할 수 있다.
2. Object remove(int index)
d -> a -> b -> c 로 만들어진 노드를 a -> b -> c 로 변경하면 된다.
-노드를 삭제했으므로 오른쪽 노드의 index가 하나씩 당겨진다.
- 배열의 경우 처 ㅅ번째 항복이 삭제되면 모든 데이터를 왼쪽으로 하나씩 밀어야 하지만 연결 리스트는 일부 참조만 변경하면 된다. 나머지 노드는 어떤 일이 일어난지도 모른다.
- 연결리스트의 첫번째 항목에 값을 삭제하는 것은 매우 빠르다. O(1)로 표현할 수 있다.
3. 중간 위치에 데이터 추가
- 노드를 추가했으므로 추가한 노드 오른쪽에 있는 노드들의 index가 하나씩 뒤로 밀려난다.
- 배열의 경우 데이터가 추가되면 인덱스 위치부터 모든 데이터를 오른쪽으로 하나씩 밀어야 하지만 연결 리스트는 새로 생성한 노드의 참조만 변경하면 된다. 나머지 노드는 어떤 일이 일어난지도 모른다.
- O(n)의 성능이다.
연결 리스트는 인덱스르 사용해서 노드를 추가할 위치를 찾는데 O(n)이 걸린다.
위치를 찾고 노드를 추가하는데 O(1)이 걸린다.
따라서 O(n+1)이기에 O(n)이 소요된다.
4. 데이터 삭제
- 노드를 삭제했으므로 오른쪽 노드의 index가 하나씩 당겨진다.
- O(n)의 성능이다.
연결리스트에서 인덱스로 삭제할 항목을 찾는데 O(n)이 걸린다.
연결리스트에서 항목을 삭제하는 것은 매우 빠르다. O(1)로 표현할 수 있다.
연결리스트와 배열 리스트 둘 다 중간에 있는 항목을 추가하거나 삭제하는 경우 둘 다 같은 O(n)이다.
이제 구현해보자.
public class MyLinkedListV2 {
private Node first;
private int size = 0;
public void add(Object o ){
Node newNode = new Node(o);
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 elemenet){
Node x = getNode(index);
Object oldValue = x.item;
x.item = elemenet;
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){
return getNode(index).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 +
'}';
}
}
MyLinkedListV1{first=[a->b->c], size=3}
첫번째 항목에 추가
MyLinkedListV1{first=[d->a->b->c], size=4}
첫번째 항목에 삭제
MyLinkedListV1{first=[a->b->c], size=3}
중간 항목에 추가
MyLinkedListV1{first=[a->e->b->c], size=4}
중간 항목에 삭제
MyLinkedListV1{first=[a->b->c], size=3}
배열 리스트 vs 연결 리스트 사용
데이터를 조회할 일이 많고, 뒷 부분에 데이터를 추가한다면 배열 리스트가 보통 더 좋은 성능을 제공한다. 앞쪽의 데이터를 추가하거나 삭제하는 일이 많다면 연결 리스트를 사용하는 것이 보통 더 좋은 성능을 제공한다.
참고 - 단일 연결 리스트, 이중 연결 리스트
우리가 구현한 연결 리스트는 한 방향으로만 이동하는 단일 연결 리스트이다. 노드를 앞뒤로 모두 연결하는 이중 연결 리스트를 사용하면 성능을 더 개선할 수 있다. 자바가 제공하는 연결 리스트는 이중 연결 리스트이다. 추가로 자바가 제공하는 연결 리스트는 마지막 노드를 참조하는 변수를 가지고 있어서, 뒤에 추가하거나 삭제하는 경우에도 O(1)의 성능을 제공한다.
직접 구현하는 연결 리스트3 - 제네릭
지금까지 만든 연결 리스트에 제네릭을 도입해서 타입 안정성을 높혀보자.
추가로 여기서 사용하는 Node는 외부에서 사용되는 것이 아니라 연결 리스트 내부에서만 사용된다. 따라서 중첩 클래스로 만들자.
public class MyLinkedListV3<E> {
private Node<E> first;
private int size = 0;
public void add(E o ){
Node<E> newNode = new Node<>(o);
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 elemenet){
Node<E> x = getNode(index);
E oldValue = x.item;
x.item = elemenet;
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){
return (E) getNode(index).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 "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){
sb.append(x.item);
if(x.next != null){
sb.append("->");
}
x = x.next;
}
sb.append("]");
return sb.toString();
}
}
}
public static void main(String[] args) {
MyLinkedListV3<String> stringList = new MyLinkedListV3<>();
stringList.add("a");
stringList.add("b");
stringList.add("c");
String string = stringList.get(0);
System.out.println("string = " + string);
MyLinkedListV3<Integer> intList = new MyLinkedListV3<>();
intList.add(1);
intList.add(2);
intList.add(3);
Integer integer = intList.get(0);
System.out.println("integer = " + integer);
}
제네릭이 사용되어 타입 안정성이 높아진 것을 확인할 수 있다.
'공부 > Java' 카테고리의 다른 글
| 자바 컬렉션 프레임워크 - 해시(Hash) (2) | 2024.09.28 |
|---|---|
| 자바 컬렉션 프레임워크 List (0) | 2024.09.27 |
| 자바 컬렉션 프레임워크 - ArrayList (1) | 2024.09.25 |
| 자바 제네릭(Generic) 2편 (0) | 2024.09.24 |
| 자바 제네릭(Generic) 1편 (1) | 2024.09.23 |