* 이중 연결 리스트 (Doubly Linked List)
- 양쪽 방향으로 순회할 수 있도록 연결한 리스트
원형 연결 리스트에서 현재 노드의 바로 이전 노드에 접근하려면 전체 리스트를 한바퀴 순회해야 하는 문제를 해결
[ 삽입연산 ]
(1) 삽입할 노드를 가져온다.
(2) 새 노드의 데이터 필드에 값을 저장한다.
(3) 새 노드의 왼쪽 노드의 오른쪽 링크(rlink)를 새 노드의 오른쪽 링크(rlink)에 저장한다.
(4) 그리고 왼쪽 노드의 오른쪽 링크(rlink)에 새 노드를 주소를 저장한다.
(5) 새 노드의 오른쪽 노드의 왼쪽 링크(llink)를 새 노드의 왼쪽 링크(llink)에 자장한다.
(6) 그리고 오른쪽 노드의 왼쪽 링크(llink)에 새 노드의 주소를 저장한다.
[ 삭제연산 ]
(1) 삭제할 노드의 오른쪽 노드의 주소(old.rlink)를 삭제할 노드의 왼쪽 노드(old.llink)의 오른쪽 링크(rlink)에 저장한다.
(2) 삭제할 모드의 왼쪽 노드의 주소(old.llink)를 삭제할 노드의 오른쪽 노드(old.rlink)의 왼쪽 링크(llink)에 저장한다.
(3) 삭제한 노드를 자유공간 리스트에 반환한다.
|
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 |
Test.java
package DoublyLinkedList;
public class Test {
public static void main(String[] args) {
DoublyLinkedList list = new DoublyLinkedList();
System.out.println("(1) 공백 리스트에 노드 3개 삽입하기");
list.insertLastNode("월");
list.insertLastNode("수");
list.insertLastNode("일");
list.printList();
System.out.println("(2) \"수\"노드 뒤에 \"금\" 노드 삽입하기");
ListNode pre = list.searchNode("수");
if(pre==null){
System.out.println("검색 실패 >> 찾는 데이터가 없습니다.");
}else{
list.insertMiddleNode(pre, "금");
}
list.printList();
System.out.println("(3) 리스트의 첫번째에 노드 추가하기");
list.insertFirstNode("토");
list.printList();
System.out.println("(4) 리스트의 마지막 노드 삭제하기");
list.deleteLastNode();
list.printList();
System.out.println("(5) 리스트의 중간 노드 \"수\" 삭제하기");
list.deleteMiddleNode("수");
list.printList();
System.out.println("(6) 리스트의 첫번째 노드 삭제하기");
list.deleteFirstNode();
list.printList();
}
} |
|
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 |
ListNode.java
package DoublyLinkedList;
public class ListNode {
ListNode prev;
String data;
ListNode next;
public ListNode(){
this.prev = null;
this.data = null;
this.data = null;
}
public ListNode(String data){
this.data = data;
}
public ListNode(ListNode prev, String data, ListNode next) {
super();
this.prev = prev;
this.data = data;
this.next = next;
}
public String getData(){
return this.data;
}
} |
|
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
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138 |
DoublyLinkedList.java
package DoublyLinkedList;
public class DoublyLinkedList {
ListNode head;
public DoublyLinkedList() {
this.head = null;
}
public void insertFirstNode(String data){
ListNode node = new ListNode(data);
if(head==null){
head = node;
node.prev = node;
node.next = node;
}else{
ListNode current = head;
ListNode prev = current.prev;
node.prev = prev;
node.next = current;
current.prev = node;
prev.next = node;
head = node;
}
}
public void insertMiddleNode(ListNode prev, String data){
ListNode node = new ListNode(data);
if(head==null){
head = node;
node.prev = node;
node.next = node;
}else{
ListNode current = head;
while(current != prev){
current = current.next;
}
ListNode next = current.next;
node.next = next;
node.prev = current;
current.next = node;
next.prev = node;
}
}
public void insertLastNode(String data){
ListNode node = new ListNode(data);
if(head==null){
head = node;
node.prev = node;
node.next = node;
}else{
ListNode current = head;
while(current.next!=head){
current = current.next;
}
ListNode next = current.next;
node.next = next;
next.prev = node;
current.next = node;
node.prev = current;
}
}
public void deleteFirstNode(){
if(head==null){
System.out.println("삭제할 리스트가 존재하지 않습니다.");
}else{
ListNode current = head;
ListNode prev = current.prev;
ListNode next = current.next;
next.prev = prev;
prev.next = next;
head = next;
}
}
public void deleteMiddleNode(String data){
if(head==null){
System.out.println("삭제할 리스트가 존재하지 않습니다.");
}else{
ListNode current = head;
while(current.data != data){
current = current.next;
}
ListNode prev = current.prev;
ListNode next = current.next;
prev.next = next;
next.prev = prev;
}
}
public void deleteLastNode(){
if(head==null){
System.out.println("삭제할 리스트가 존재하지 않습니다.");
}else{
ListNode current = head;
while(current.next!=head){
current = current.next;
}
ListNode prev = current.prev;
ListNode next = current.next;
prev.next = next;
next.prev = prev;
}
}
public ListNode searchNode(String data){
if(head==null){
return null;
}else{
ListNode current = head;
while(current.data != data){
current = current.next;
}
return current;
}
}
public void printList(){
if(head==null){
System.out.println("출력할 내용이 존재하지 않습니다.");
}else{
ListNode current = head;
while(current.next!=head){
System.out.print(current.data + " ");
current = current.next;
}
System.out.print(current.data);
}
System.out.println();
}
} |
'전산 기초 > 자료구조' 카테고리의 다른 글
| [자료구조/java] 스택 (Stack) - 1차원 배열, 연결리스트 구현 (0) | 2015.10.31 |
|---|---|
| [자료구조/java] 다항식의 연결 자료구조 표현 (0) | 2015.10.30 |
| [자료구조/java] 원형 연결 리스트 (Circular Linked List) (0) | 2015.10.26 |
| [자료구조/java] 단순 연결 리스트 (Linked List) (0) | 2015.10.25 |
| [자료구조] 자료구조 시작 (0) | 2015.10.24 |
