1. 노드와 연결
배열 리스트의 단점
- 배열 리스트는 내부에 배열을 사용해서 데이터를 보관하고 관리함
배열의 사용하지 않는 공간 낭비
- 이로인해 배열은 필요한 크기를 미리 확보해야 함
- 데이터가 얼마나 추가될지 예측할 수 없는 경우 나머지 공간은 사용되지 않고 낭비됨
배열의 중간에 데이터 추가
- 배열의 앞이나 중간에 데이터를 추가하면 추가할 데이터의 공간을 확보하기 위해 기존 데이터들을 오른쪽으로 이동해야 함
- 그리고 삭제의 경우에는 빈 공간을 채우기 위해 왼쪽으로 이동해야 함
- 이렇게 앞이나 중간에 데이터를 추가하거나 삭제하는 경우 많은 데이터를 이동해야 하기 때문에 성능이 좋지 않음
노드와 연결
- 낭비되는 메모리 없이 딱 필요한 만큼만 메모리를 확보해서 사용하고, 또 앞이나 중간에 데이터를 추가하거나 삭제할 때도 효율적인 자료 구조가 있는데, 바로 노드를 만들고 각 노드를 서로 연결하는 방식임
노드 클래스
public class Node {
Object item;
Node next;
}- 노드 클래스는 내부에 저장할 데이터인
item과 다음으로 연결할 노드의 참조인next를 가짐 - 이 노드 클래스를 사용해서 데이터 A, B, C를 순서대로 연결
노드에 데이터 A, B 추가
- Node 인스턴스를 생성하고 item에 A를 넣음
- B 또한 Node 인스턴스를 생성하고 item에 B를 넣음
- 처음 만든 노드의 Node next 필드에 새로 만든 노드의 참조값을 넣음
- 이렇게하면 첫 번째 노드와 두 번째 노드가 서로 연결됨
- 첫 번째 노드의 node.next를 호출하면 두 번째 노드를 구할 수 있음
package collection.link;
public class Node {
Object item;
Node next;
public Node(Object item) {
this.item = item;
}
}- 필드의 접근 제어자는 private으로 선언하는 것이 좋지만, 이 예제에서는 설명을 단순하게 하기 위해 디폴트 접근 제어자를 사용함
package collection.link;
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("모든 노트 탐색하기");
Node x = first;
while (x != null) {
System.out.println(x.item);
x = x.next;
}
}
}실행결과
모든 노드 탐색하기
A
B
C
1. Node first = new Node("A")
- Node 인스턴스를 생성하고 item에 "A"를 넣어줌
- Node first = x01
- first 변수에 생성된 노드의 참조를 보관
- first 변수는 이름 그대로 첫 번째 노드의 참조를 보관함
1. first.next = new Node("B")
- Node 인스턴스를 생성하고 item에 "B"를 넣어줌
- first.next = x02
- 처음 만든 노드의 next 필드에 새로 만든 노드의 참조값을 넣어줌
- 이렇게하면 첫 번째 노드와 두 번째 노드가 서로 연결됨
1. first.next.next = new Node("C")
2. first.next.next = x03
3. x01.next.next = x03
4. x02.next = x03
- 두 번째 만든 노드의 Nodex next 필드에 새로 만든 노드의 참조값을 넣어줌
- 이렇게하면 두 번째 노드와 세 번째 노드가 서로 연결됨
연결된 노드를 찾는 방법
- Node first를 통해 첫 번째 노드를 구할 수 잇음
- 첫 번째 노드의 node.next를 호출하면 두 번째 노드를 구할 수 있음
- 두 번째 노드의 node.next를 호출하면 세 번째 노드를 구할 수 있음
- 첫 번째 노드의 node.next.next를 호출하면 세 번째 노드를 구할 수 있음
모든 노드 탐색하기
Node x = first;
while (x != null) {
System.out.println(x.item);
x = x.next;
}A
B
C- Node x는 처음 노드부터 순서대로 이동하면서 모든 노드를 가리킴
- 처음에 Node x는 x01를 참조함
- 그리고 while문을 통해 반복해서 다음 노드를 가리킴
- while문은 다음 노드가 없을 때까지 반복함
- Node.next의 참조값이 null이면 노드의 끝임
Backend development