기본 연결 리스트에서 이전 노드를 가리키는 prev 변수 필요 - 기존에 구현한 연결 리스트에서는 삭제할 노드의 이전 노드와 삭제할 노드의 다음 노드를 사로 연결해주기 위해 앞에서부터 탐색하여 이전 노드를 찾음 (첫번째부터 탐색을 진행하기 때문에 데이터가 많아질수록 부하가 발생) - 양방향 연결 리스트의 경우 이전 노드를 바로 알 수 있기 때문에 성능상 이점이 있음
추상 자료형
자료형
반환값
내용
initialize()
void
리스트 초기화
insert(Data)
boolean
리스트에 데이터 삽입
first()
Data
첫번째 데이터를 가리키도록 함 (Dummy 노드를 추가한 경우 반환값을 받을 필요 없으나, 기본 연결 리스트 구현 시에는 필요하기 때문에 반환값을 Data로 주었음)
next()
Data
현재 참조하고 있는 데이터의 다음 데이터를 가리키도록 하며 해당 값을 반환
remove()
Data
현재 참조하고 있는 데이터를 삭제
count()
int
리스트에 있는 데이터의 총 개수
리스트 초기화 - 헤드가 더미를 가리키게 함
public void initialize() {
head = new Node();
cur = head;
countOfData = 0;
}
데이터 추가 - 2와 4를 추가했을 때의 상태
public boolean insert(Object data) {
try {
Node newNode = new Node();
newNode.data = data;
// 헤드의 nextNode가 null이 아닐 경우
// 즉, 데이터가 하나라도 추가된 경우를 뜻함
if (head.nextNode != null) {
head.nextNode.prevNode = newNode;
}
// 새로운 노드의 다음 노드는 기존에 head가 가리키던 nextNode를 받음
newNode.nextNode = head.nextNode;
// 새로운 노드의 이전 노드는 머리를 가리켜야 함
newNode.prevNode = head;
// 헤드의 다음 노드는 새로운 노드를 가리킴
head.nextNode = newNode;
countOfData++;
return true;
}catch (Exception ex){
System.out.println(ex.getMessage());
return false;
}
}
데이터 삭제 - 4를 삭제했을 경우 - 삭제할 노드의 이전 노드의 다음 노드가 가리키는 값을 삭제할 노드의 다음 노드 값으로 변경 - 삭제할 노드의 다음 노드의 이전 노드가 가리키는 값을 삭제할 노드의 이전 노드 값으로 변경
public Object remove() {
if (countOfData == 0){
System.out.println("삭제할 노드가 없습니다.");
return null;
}
Node rNode = cur;
// 현재 노드의 이전 노드가 가리키는 다음 노드를 현재 노드의 다음 노드로 변경
cur.prevNode.nextNode = cur.nextNode;
if (cur.nextNode != null) {
cur.nextNode.prevNode = cur.prevNode;
}
countOfData--;
return rNode;
}
데이터 조회 - first 호출 시 - next 호출 시
구현
디렉토리 구조
인터페이스 구현 - 기존 순차 리스트 인터페이스와 동일
package List;
// 다형성을 위해 List를 인터페이스로 생성
public interface List {
// 리스트 초기화
void initialize();
// 리스트에 데이터 삽입 (어떤 값이 올 지 모르므로 Object를 인자로 받음)
boolean insert(Object data);
// 첫 번째 데이터를 가리키도록 하며 값을 반환
Object first();
// 현재 참조하고 있는 데이터의 다음 데이터를 가리키도록 하며 값을 반환
Object next();
// 현재 참조하고 있는 데이터를 지움
Object remove();
// 리스트에 저장된 데이터의 개수를 반환
int count();
}
양방향 연결 리스트 구현
package List.LinkedList.Double;
import List.List;
public class DoublyLinkedList implements List {
public class Node {
public Object data;
public Node prevNode;
public Node nextNode;
}
Node head = null;
Node cur = null;
int countOfData = 0;
@Override
public void initialize() {
head = new Node();
cur = head;
countOfData = 0;
}
@Override
public boolean insert(Object data) {
try {
Node newNode = new Node();
newNode.data = data;
// 헤드의 nextNode가 null이 아닐 경우
// 즉, 데이터가 하나라도 추가된 경우를 뜻함
if (head.nextNode != null) {
head.nextNode.prevNode = newNode;
}
// 새로운 노드의 다음 노드는 기존에 head가 가리키던 nextNode를 받음
newNode.nextNode = head.nextNode;
// 새로운 노드의 이전 노드는 머리를 가리켜야 함
newNode.prevNode = head;
// 헤드의 다음 노드는 새로운 노드를 가리킴
head.nextNode = newNode;
countOfData++;
return true;
}catch (Exception ex){
System.out.println(ex.getMessage());
return false;
}
}
@Override
public Object first() {
// 현재 위치를 가지고 있는 cur 변수를 head로 설정 (맨 처음 위치로)
cur = head;
return cur;
}
@Override
public Object next() {
// 현재 가리키고 있는 노드의 다음 노드가 null인 경우 마지막 노드로 판단
if (cur.nextNode == null){
System.out.println("마지막 노드입니다.");
return null;
}
// 현재 가리키고 있는 노드의 다음 노드로 설정
cur = cur.nextNode;
return cur.data;
}
@Override
public Object remove() {
if (countOfData == 0){
System.out.println("삭제할 노드가 없습니다.");
return null;
}
Node rNode = cur;
// 현재 노드의 이전 노드가 가리키는 다음 노드를 현재 노드의 다음 노드로 변경
cur.prevNode.nextNode = cur.nextNode;
if (cur.nextNode != null) {
cur.nextNode.prevNode = cur.prevNode;
}
countOfData--;
return rNode;
}
@Override
public int count() {
return countOfData;
}
}
메인 구현 - 데이터 추가/삭제/조회 기능 테스트
package List.LinkedList.Double;
public class DoublyLinkedListMain {
public static void main(String[] args) {
DoublyLinkedList linkedList = new DoublyLinkedList();
// 리스트 초기화
linkedList.initialize();
// 리스트에 데이터 삽입
linkedList.insert(1); linkedList.insert(2);
linkedList.insert(3); linkedList.insert(4);
linkedList.insert(5); linkedList.insert(6);
// 첫번째 노드로 설정
Object data = null;
linkedList.first();
// data가 null이 될 때까지 반복
while((data = linkedList.next()) != null) {
System.out.println(data);
}
// 데이터 삭제
Object remove = null;
linkedList.first();
while((data = linkedList.next()) != null){
if ((int)data == 1){
remove = linkedList.remove();
System.out.println((int)data + "가 삭제되었습니다.");
remove = null;
}
}
// 첫번째 노드로 설정
linkedList.first();
// data가 null이 될 때까지 반복
while((data = linkedList.next()) != null) {
System.out.println(data);
}
}
}
