데이터들을 Node로 관리 (Node : data, 다음 노드의 주소값으로 이루어져 있음)
리스트는 데이터의 저장 순서를 유지해야하는 자료구조가 아님
Node
리스트의 구성
필요한 Node들 head : 리스트의 머리를 가리킴 tail : 리스트의 꼬리를 가리킴 cur : 데이터의 조회에 사용됨
head에 데이터 추가 시 장점 : tail 노드가 불필요 단점 : 저장 순서가 유지되지 않음
tail에 데이터 추가 시 장점 : 저장 순서가 유지됨 단점 : tail 노드가 필요
데이터 추가 tail 또는 head쪽에 데이터 추가 후 tail 또는 head가 가리키는 값 변경 ex) tail에 데이터 추가 시
데이터 조회 cur Node를 이용해 조회 ex) data2 조회
데이터 삭제 삭제할 노드를 가리키고 있는 노드의 next 값을 삭제할 노드가 가진 next 값으로 변경
추상 자료형 (ADT)
자료형
반환값
내용
initialize()
void
리스트 초기화
insert(Node)
boolean
리스트에 데이터 저장
next()
Node
현재 가리키고 있는 노드의 다음 노드
remove()
Node
현재 가리키고 있는 노드를 삭제
count()
int
현재 리스트에 있는 데이터의 개수
구현
디렉토리 구조
인터페이스 구현 다형성을 위해 List관련 메소드를 인터페이스로 구현
package List;
// 다형성을 위해 List를 인터페이스로 생성
public interface List {
// 리스트 초기화
void initialize();
// 리스트에 데이터 삽입 (어떤 값이 올 지 모르므로 Object를 인자로 받음)
boolean insert(Object data);
// 첫 번째 데이터를 가리키도록 하며 값을 반환
Object first();
// 현재 참조하고 있는 데이터의 다음 데이터를 가리키도록 하며 값을 반환
Object next();
// 현재 참조하고 있는 데이터를 지움
Object remove();
// 리스트에 저장된 데이터의 개수를 반환
int count();
}
단일 연결 리스트 구현 실제 단일 연결 리스트 구현
package List.LinkedList.Single;
import List.List;
public class SingleLinkedList implements List {
public class Node {
Object data;
Node nextNode;
public Node(Object data, Node nextNode){
this.data = data;
this.nextNode = nextNode;
}
public Node() {
this.data = null;
this.nextNode = null;
}
}
Node head = null;
Node tail = null;
Node cur = null;
Node newNode = null;
int dataCount = 0;
@Override
public void initialize() {
head = null;
tail = null;
cur = null;
newNode = null;
}
@Override
public boolean insert(Object data) {
try {
newNode = new Node(data, null);
if (head == null) {
head = newNode;
} else {
tail.nextNode = newNode;
}
tail = newNode;
dataCount++;
return true;
}catch (Exception ex){
return false;
}
}
@Override
public Object first() {
try {
if (head == null) {
return null;
}
cur = head;
return cur.data;
}catch (Exception ex){
return null;
}
}
@Override
public Object next() {
try{
if (head == null){
return null;
}
if (cur.nextNode == null){
System.out.println("마지막 노드입니다.");
return null;
}
cur = cur.nextNode;
return cur.data;
}catch (Exception ex) {
return null;
}
}
@Override
public Object remove() {
try{
if (head == null){
return null;
}
Node tmpNode = head;
while(tmpNode.nextNode != cur){
tmpNode = tmpNode.nextNode;
}
tmpNode.nextNode = cur.nextNode;
dataCount--;
return cur;
}catch (Exception ex){
return null;
}
}
@Override
public int count() {
return dataCount;
}
}
메인 구현 데이터 삽입, 삭제 및 조회 기능 테스트
package List.LinkedList.Single;
public class SingleLinkedListMain {
public static void main(String[] args) {
SingleLinkedList linkedList = new SingleLinkedList();
// 리스트 초기화
linkedList.initialize();
// 리스트에 데이터 삽입
linkedList.insert(1); linkedList.insert(2);
linkedList.insert(3); linkedList.insert(4);
linkedList.insert(5); linkedList.insert(6);
// 첫번째 노드로 설정 및 데이터 가져오기
Object data = linkedList.first();
System.out.println(data);
// data가 null이 될 때까지 반복
while((data = linkedList.next()) != null) {
System.out.println(data);
}
// 데이터 삭제
Object remove = null;
data = linkedList.first();
if ((int)data == 4){
remove = linkedList.remove();
System.out.println((int)data + "가 삭제되었습니다.");
remove = null;
}
while((data = linkedList.next()) != null){
if ((int)data == 4){
remove = linkedList.remove();
System.out.println((int)data + "가 삭제되었습니다.");
remove = null;
}
}
// 첫번째 노드로 설정 및 데이터 가져오기
data = linkedList.first();
System.out.println(data);
// data가 null이 될 때까지 반복
while((data = linkedList.next()) != null) {
System.out.println(data);
}
}
}
더미노드를 이용한 단순 연결 리스트
기존 연결 리스트에서는 head가 첫 번째 노드를 가리키고 있음 Dummy Node 이용 시 head가 더미 노드를 가리키고 있음
노드들을 추가/삭제 및 조회 시 첫 번째 노드와 두 번째 이후의 노드간 차이가 있음 - 첫번째 노드를 먼저 가져와서 처리한 후 next 메소드로 다음 노드를 참조하는 방식
