반응형
안녕들 하시죠!
이번시간에는 Java 언어를 사용해 링크드리스트(이중 연결 리스트)를 구현해보겠습니다.
아래에는 제가 사용할 클래스와 메소드입니다.
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
|
public class LinkedList {
Node head;
Node rear;
int size = 0;
void firstNode(int data) {} // 첫번째 Node 생성
void addRearNode(int data) {} // 뒷단에 Node 삽입
void addHeadNode(int data) {} // 앞단에 Node 삽입
int readData(int index) {} // 특정 데이터 읽기
void printData() {} // 전체 데이터 출력
boolean removeNode(int index) {} // 특정 노드 삭제
boolean removeAllNode() {} // 전체 노드 삭제
class Node {
Node(int data) {
this.data = data;
}
int data;
Node front = null;
Node back = null;
}
}
|
cs |
기본적인 Node의 구성입니다.
값이 들어있는 data, 앞에있는 Node를 가리키고 있는 front, 뒤에있는 Node를 가리키고 있는 back
앞에있는 Node를 head, 뒤에있는 Node를 rear라고 구성합니다.
- void firstNode
|
1
2
3
4
5
6
7
|
void firstNode(int data) {
Node newNode = new Node(data);
head = newNode;
rear = newNode;
size++;
System.out.println("firstNode(int data) 실행");
}
|
cs |
Node가 한개도 없는 상황에서 첫번째 Node를 생성하는 메소드입니다.
앞,뒤에 어떤 Node도 존재하지 않기 때문에 head와 rear 둘다 첫번째 Node를 가리키게 됩니다.
Node가 생성되었으니 size를 증가시켜줍니다.
- void addRearNode
|
1
2
3
4
5
6
7
8
9
10
11
12
|
void addRearNode(int data) {
if (size != 0) {
Node newNode = new Node(data);
rear.back = newNode; // ①
newNode.front = rear; // ②
rear = newNode; // ③
size++;
System.out.println("addRearNode(int data) 실행");
} else {
System.out.println("firstNode(int data) 실행시켜주세요");
}
}
|
cs |
맨뒤에 Node를 삽입하는 메소드입니다.
간단하게 생각하면,
현재 맨뒤를 가리키고 있는 rear의 뒷자리에 새로운 Node를 삽입하고 서로 가리키고있는 화살표를 바꿔주고 맨뒤에 새로 삽입된 Node를 rear로 만들어주는 과정입니다.
① : rear의 back의 뒤로 향하는 화살표를 새로 삽입될 newNode를 가리키게 만든다. ( rear.back = newNode )
② : 새로 삽입될 newNode의 앞으로 향하는 화살표를 현재 rear를 가리키게 만든다. ( newNode.front = rear )
③ : 화살표를 바꿔 서로 가리키게 만들었으니 새로 삽입될 newNode를 맨뒤(rear)로 만들어준다. ( rear = newNode )
- void addHeadNode
앞에서 설명한 addRearNode와 비슷하게 이번엔 맨앞단에 Node를 삽입하는 메소드입니다.
|
1
2
3
4
5
6
7
8
9
10
11
12
|
void addHeadNode(int data) {
if (size != 0) {
Node newNode = new Node(data);
head.front = newNode; // 현재 가장 앞에있는 head Node의 앞으로 향하는 화살표가 새로 삽입될 newNode를 가리키게 만든다.
newNode.back = head; // 새로 삽입될 newNode의 뒤로 향하는 화살표가 현재 head인 Node를 가리키게 만든다.
head = newNode; // 새로 삽입될 newNode를 맨앞(head)로 만들어준다.
size++;
System.out.println("맨앞에 " + data + " 들어감");
} else {
firstNode(data); // 현재 삽입되어있는 Node가 없다면 새로 추가.
}
}
|
cs |
- int readData
특정 Node의 data 읽기.
|
1
2
3
4
5
6
7
8
9
10
11
12
13
|
int readData(int index) {
int result = 0;
try {
Node node = head; // 맨앞 Node 부터 시작.
for (int i = 1; i < index; i++) {
node = node.back; // 한칸씩 뒤로 이동하며 특정위치(index)를 찾고, 값을 result에 저장.
}
result = node.data;
} catch (Exception e) {
System.out.println("Exception 발생");
}
return result;
}
|
cs |
- void printData
전체 Node의 data 출력.
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
|
void printData() {
if (size > 0) {
try {
Node node = head; // 맨앞 Node부터 시작.
for (int i = 0; i < size; i++) {
System.out.print(node.data + " ");
node = node.back; // 한칸씩 뒤로 이동하며 모든 Node의 data 출력.
}
} catch (Exception e) {
System.out.println("Exception 발생");
}
} else {
System.out.println("출력데이터가 없습니다.");
}
}
|
cs |
- boolean removeNode
특정위치의 Node 삭제.
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
|
boolean removeNode(int index) {
if ((index <= size && index > 0) && size > 0) {
if (index == 1) {// head를 지울때
head = head.back; // head를 뒤로 한칸 옮긴다.
head.front = null;
} else if (index == size) {// rear를 지울때
rear = rear.front; // rear를 한칸 앞으로 옮긴다.
rear.back = null;
} else { // head나 rear가 아닌 중간에 있는 Node를 지울때
Node node = head;
for (int i = 1; i < index; i++) {
node = node.back;
}
node.front.back = node.back; // ①
node.back.front = node.front;
}
size--;
return true;
} else {
System.out.println("index 범위X");
return false;
}
}
|
cs |
① : 중간에 있는 Node를 삭제했으니, 앞 뒤의 Node들을 화살표로 연결해 주는 과정입니다.
- boolean removeAllNode
전체 Node 삭제.
|
1
2
3
4
5
6
|
boolean removeAllNode() {
head = null;
rear = null;
size = 0;
return true;
}
|
cs |
LinkedList 전체 코드
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
|
public class Linkedlist {
Node head;
Node rear;
int size = 0;
// 아무것도 없는 상태에서 새로운 Node 추가
void firstNode(int data) {
Node newNode = new Node(data);
head = newNode;
rear = newNode;
size++;
System.out.println("firstNode(int data) 실행");
}
// 뒷단에 Node 추가
void addRearNode(int data) {
if (size != 0) {
Node newNode = new Node(data);
rear.back = newNode; // ①
newNode.front = rear; // ②
rear = newNode; // ③
size++;
System.out.println("addRearNode(int data) 실행");
} else {
System.out.println("firstNode(int data) 실행시켜주세요");
}
}
// 맨앞단에 Node 추가
void addHeadNode(int data) {
if (size != 0) {
Node newNode = new Node(data);
head.front = newNode; // 현재 가장 앞에있는 head Node의 앞으로 향하는 화살표가 새로 삽입될 newNode를 가리키게 만든다.
newNode.back = head; // 새로 삽입될 newNode의 뒤로 향하는 화살표가 현재 head인 Node를 가리키게 만든다.
head = newNode; // 새로 삽입될 newNode를 맨앞(head)로 만들어준다.
size++;
System.out.println("맨앞에 " + data + " 들어감");
} else {
firstNode(data); // 현재 삽입되어있는 Node가 없다면 새로 추가.
}
}
// 특정 위치(index) Node Data 읽기
int readData(int index) { // 특정 노드의 data 읽기
int result = 0;
try {
Node node = head; // 맨앞 Node 부터 시작.
for (int i = 1; i < index; i++) {
node = node.back; // 한칸씩 뒤로 이동하며 특정위치(index)를 찾고, 값을 result에 저장.
}
result = node.data;
} catch (Exception e) {
System.out.println("Exception 발생");
}
return result;
}
// 전체 노드의 data 출력
void printData() {
if (size > 0) {
try {
Node node = head; // 맨앞 Node부터 시작.
for (int i = 0; i < size; i++) {
System.out.print(node.data + " ");
node = node.back; // 한칸씩 뒤로 이동하며 모든 Node의 data 출력.
}
} catch (Exception e) {
System.out.println("Exception 발생");
}
} else {
System.out.println("출력데이터가 없습니다.");
}
}
// 특정 위치(index) Node 삭제
boolean removeNode(int index) {
if ((index <= size && index > 0) && size > 0) {
if (index == 1) {// head를 지울때
head = head.back; // head를 뒤로 한칸 옮긴다.
head.front = null;
} else if (index == size) {// rear를 지울때
rear = rear.front; // rear를 한칸 앞으로 옮긴다.
rear.back = null;
} else { // head나 rear가 아닌 중간에 있는 Node를 지울때
Node node = head;
for (int i = 1; i < index; i++) {
node = node.back;
}
node.front.back = node.back; // ①
node.back.front = node.front; // ②
}
size--;
return true;
} else {
System.out.println("index 범위X");
return false;
}
}
// 전체 Node 삭제
boolean removeAllNode() {
head = null;
rear = null;
size = 0;
return true;
}
class Node {
Node(int data) {
this.data = data;
}
int data;
Node front = null;
Node back = null;
}
}
|
cs |
오늘은 여기까지입니다 감사합니다 !
'알고리즘' 카테고리의 다른 글
| Java) 입력받은 숫자 n까지의 소수갯수 구하기 + 최적 알고리즘 (0) | 2019.09.27 |
|---|---|
| Java 원형큐 구현 (0) | 2019.06.23 |
| 백준 10828번 (스택) (0) | 2019.05.10 |
| 백준 2750번 (버블정렬) (0) | 2019.05.01 |
| 백준 1000번 (0) | 2019.04.16 |
