IntNode 클래스
2025. 4. 19. 19:44ㆍ자료구조
코드 설명
/******************************************************************************
* IntNode 클래스는 정수 데이터를 담는 연결 리스트의 노드를 제공합니다.
*
* @note
* 노드로 이루어진 리스트는 힙 메모리만 허용한다면 길이에 제한 없이 만들 수 있습니다.
* 하지만 Integer.MAX_VALUE(2,147,483,647)를 초과하는 노드 수에 대해
* listLength 메서드는 정수 오버플로우 때문에 올바른 결과를 반환하지 않을 수 있습니다.
******************************************************************************/
public class IntNode {
// IntNode 클래스의 불변 조건 (Invariant):
// 1. 이 노드의 정수 데이터는 data 인스턴스 변수에 저장됩니다.
// 2. 리스트의 마지막 노드는 link가 null입니다.
// 그렇지 않으면 link는 다음 노드를 참조합니다.
private int data;
private IntNode link;
/**
* 생성자: 주어진 데이터와 링크를 가진 노드를 초기화합니다.
*/
public IntNode(int initialData, IntNode initialLink) {
data = initialData;
link = initialLink;
}
/**
* 현재 노드 뒤에 새로운 노드를 추가합니다. 새 노드에는 주어진 데이터가 저장됩니다.
*/
public void addNodeAfter(int item) {
link = new IntNode(item, link);
}
/**
* 이 노드에 저장된 데이터를 반환합니다.
*/
public int getData() {
return data;
}
/**
* 이 노드가 가리키는 다음 노드의 참조를 반환합니다.
*/
public IntNode getLink() {
return link;
}
/**
* 주어진 시작 노드(source)부터 시작하는 연결 리스트를 복사하여 반환합니다.
*/
public static IntNode listCopy(IntNode source) {
IntNode copyHead;
IntNode copyTail;
if (source == null)
return null;
copyHead = new IntNode(source.data, null);
copyTail = copyHead;
while (source.link != null) {
source = source.link;
copyTail.addNodeAfter(source.data);
copyTail = copyTail.link;
}
return copyHead;
}
/**
* 리스트를 복사하고 복사된 리스트의 머리(head)와 꼬리(tail)를 배열로 반환합니다.
*/
public static IntNode[] listCopyWithTail(IntNode source) {
IntNode copyHead;
IntNode copyTail;
IntNode[] answer = new IntNode[2];
if (source == null)
return answer; // 기본적으로 null이 채워진 배열 반환
copyHead = new IntNode(source.data, null);
copyTail = copyHead;
while (source.link != null) {
source = source.link;
copyTail.addNodeAfter(source.data);
copyTail = copyTail.link;
}
answer[0] = copyHead;
answer[1] = copyTail;
return answer;
}
/**
* 주어진 리스트의 노드 수를 반환합니다.
*/
public static int listLength(IntNode head) {
IntNode cursor;
int answer = 0;
for (cursor = head; cursor != null; cursor = cursor.link)
answer++;
return answer;
}
/**
* start 노드부터 end 노드까지 복사한 리스트를 생성해 [head, tail]을 반환합니다.
*/
public static IntNode[] listPart(IntNode start, IntNode end) {
IntNode copyHead;
IntNode copyTail;
IntNode cursor;
IntNode[] answer = new IntNode[2];
copyHead = new IntNode(start.data, null);
copyTail = copyHead;
cursor = start;
while (cursor != end) {
cursor = cursor.link;
if (cursor == null)
throw new IllegalArgumentException("end 노드가 리스트에 없습니다.");
copyTail.addNodeAfter(cursor.data);
copyTail = copyTail.link;
}
answer[0] = copyHead;
answer[1] = copyTail;
return answer;
}
/**
* 리스트의 특정 위치에 있는 노드를 반환합니다 (1부터 시작하는 인덱스).
*/
public static IntNode listPosition(IntNode head, int position) {
if (position <= 0)
throw new IllegalArgumentException("position은 양수여야 합니다.");
IntNode cursor = head;
for (int i = 1; i < position && cursor != null; i++)
cursor = cursor.link;
return cursor;
}
/**
* 주어진 데이터를 가진 첫 번째 노드를 찾고 그 노드를 반환합니다.
*/
public static IntNode listSearch(IntNode head, int target) {
for (IntNode cursor = head; cursor != null; cursor = cursor.link)
if (target == cursor.data)
return cursor;
return null;
}
/**
* 현재 노드의 다음 노드를 제거합니다.
*/
public void removeNodeAfter() {
link = link.link;
}
/**
* 현재 노드의 데이터를 새 값으로 설정합니다.
*/
public void setData(int newData) {
data = newData;
}
/**
* 현재 노드의 링크(다음 노드 참조)를 새 노드로 설정합니다.
*/
public void setLink(IntNode newLink) {
link = newLink;
}
}인스턴스 멤버
private int data;
private IntNode link;- data: 정수형 데이터를 저장하는 변수
- link: 내가 연결하고 있는 IntNode를 저장해 준다.
생성자
public IntNode(int initialData, IntNode initialLink) {
data = initialData;
link = initialLink;
}- data와 link의 초기값을 각각 대입해 준다.
- 기본적으로 IntNode는 보통 LinkedList의 기본 자료형이기 때문에 head와 tail을 확인할 필요가 있다.
- head는 LinkedList의 맨 처음 노드이다.
- tail은 LinkedList의 맨 마지막 노드이다.
head → [data: 10 | link] → [data: 20 | link] → [data: 30 | null]
↑
tail- 처음에 IntNode를 생성할 때는 다음과 같이 head를 생성해 준다.
IntNode head=new IntNode(42, null);
//데이터에 42 값을 넣어줌
//link는 아직 연결되어 있는 노드가 없으므로 null로 초기화메서드
set&&get
public int getData() {
return data;
}- 현제 노드에 저장된 데이터를 가져온다.
public IntNode getLink() {
return link;
}- 현제 노드와 연결된 노드를 참조하여서 리턴해준다.
public void setData(int newData) {
data = newData;
}- 현제 데이터를 새로운 데이터 값으로 설정해 준다.
public void setLink(IntNode newLink) {
link = newLink;
}- 현제 연결된 링크를 새로운 노드로 설정해 준다.
삽입하기!
head=new IntNode(newEntry, head);- 맨 처음에 넣을 때는 head를 활용해 주면 된다.
- head를 새로운 데이터를 newEntry로 지정해 주고, link는 현제 head가 참조하고 있는 IntNode로 지정해 준다.
- selection을 삽입하고자 하는 노드 이전의 노드로 지정해 둔다.
- section은 15의 intNode를 가리키고 있기 때문에 section.link는 10의 IntNode를 가리킨다.
Selection.addNodeAfter(42);
public void addNodeAfter(int element)
{
link=new IntNode(element, link);
}- element=42를 해주고 link=seletection.link로 해준다면 20이 가리키고 있는 30의 IntNode를 가리키게 된다.
- new IntNode(element, link)를 해준다면
- 그러고 나서 20의 link를 42의 IntNode로 변경해 주기만 하면 된다.
IntNode 지우기
haed=head.getLink()
- head의 link를 현제 링크의 다음 링크로 지정해 주면 첫 번째 노드는 자동으로 제거된다.
public void removeNodeAfter(){
link=link.link;
}
- 42를 제거하고 싶다면 이전 IntNode의 link(42 IntNode)를 다음 노드로 바꿔지면 자동으로 42를 가리키는 link가 없기 때문에 자동으로 지워진다.
길이를 구하는 메서드
public static int listLength(IntNode head) {
IntNode cursor;
int answer = 0;
for (cursor = head; cursor != null; cursor = cursor.link)
answer++;
return answer;
}- cursor를 head노드로 지정해 두고 link를 타고 이동하다가 null이 나올 때까지 연결해 준다.
특정 값을 찾는 메서드
public static IntNode listSearch(IntNode head, int target) {
for (IntNode cursor = head; cursor != null; cursor = cursor.link)
if (target == cursor.data)
return cursor;
return null;
}- cursor를 head노드로 하여서 target과 같은 data가 나올 때까지 반복해 주면 된다.
- 만약 값이 존재하지 않는 다면 null을 리턴해준다.
노드의 위치를 활용하여서 특정 IntNode를 찾는 메서드
public static IntNode listPosition(IntNode head, int position) {
if (position <= 0)
throw new IllegalArgumentException("position은 양수여야 합니다.");
IntNode cursor = head;
for (int i = 1; i < position && cursor != null; i++)
cursor = cursor.link;
return cursor;
}- position이 0보다 같거나 작다면 IllegalArgumentException을 발생시킨다. (위치, 즉 인덱스는 0보다 커야 함)
- 그리고 position보다 작고, cursor의 값이 null이 아닐 때까지 반복해 준다.
LinkedList 복사하기(중요?)
- source가 null인 경우에는 null을 리턴해준다.
- source의 IntNode를 CopyHead와 CopyTail에 초기에 저장해 둔다.
- CopyTail.addNodeAfter(source.data)로 데이터와 link를 업데이트해준다.
- CopyTail=CopyTail.link로 지정해 준다.
public static IntNode listCopy(IntNode source) {
IntNode copyHead;
IntNode copyTail;
if (source == null)
return null;
copyHead = new IntNode(source.data, null);
copyTail = copyHead;
while (source.link != null) {
source = source.link;
copyTail.addNodeAfter(source.data);
copyTail = copyTail.link;
}
return copyHead;
}- 위의 코드는 copyHead만 리턴해준다.
public static IntNode[] listCopyWithTail(IntNode source) {
IntNode copyHead;
IntNode copyTail;
IntNode[] answer = new IntNode[2];
if (source == null)
return answer; // 기본적으로 null이 채워진 배열 반환
copyHead = new IntNode(source.data, null);
copyTail = copyHead;
while (source.link != null) {
source = source.link;
copyTail.addNodeAfter(source.data);
copyTail = copyTail.link;
}
answer[0] = copyHead;
answer[1] = copyTail;
return answer;
}- 위의 코드는 copyHead와 copyTail을 리턴해준다.
public static IntNode[] listPart(IntNode start, IntNode end) {
IntNode copyHead;
IntNode copyTail;
IntNode cursor;
IntNode[] answer = new IntNode[2];
copyHead = new IntNode(start.data, null);
copyTail = copyHead;
cursor = start;
while (cursor != end) {
cursor = cursor.link;
if (cursor == null)
throw new IllegalArgumentException("end 노드가 리스트에 없습니다.");
copyTail.addNodeAfter(cursor.data);
copyTail = copyTail.link;
}
answer[0] = copyHead;
answer[1] = copyTail;
return answer;
}- start부터 시작해서 end인 IntNode까지 복사를 해준다.
'자료구조' 카테고리의 다른 글
| 스택 활용하기 (0) | 2025.04.20 |
|---|---|
| IntStack 클래스 (0) | 2025.04.19 |
| IntLinkedBag 클래스 (0) | 2025.04.18 |
| IntArrayBag 클래스 (0) | 2025.04.18 |
| Location 클래스 (1) | 2025.04.17 |