데이터들을 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 메소드로 다음 노드를 참조하는 방식
단점 1) 배열의 길이가 사전에 정의되어야 함 2) 중간 데이터 삭제 시 해당 인덱스 이후의 값들은 한 칸씩 이동이 발생
설명
삽입 - 보통 배열의 마지막에 데이터가 삽입되며, 삽입 시 배열의 크기도 고려해야 함 - 배열의 중간에 데이터를 삽입하기 위해서는 배열의 길이가 충분한지 확인해야 하며, 삽입된 위치 뒤에 존재하는 모든 데이터들이 한 칸씩 뒤로 이동해야 하므로 중간에 데이터 삽입 시 비효율적 - 시간 복잡도 : O(n)
삭제 - 배열의 중간에 위치한 데이터를 삭제할 경우 해당 위치의 뒤 데이터들은 한 칸씩 앞으로 이동해야 하므로 배열의 크기가 크고 삭제가 빈번할수록 비효율적 - 시간복잡도 : O(n)
조회(검색) - 배열에 존재하는 데이터에 대한 인덱스 값들이 고정되어 있기 때문에 조회가 간편함 - 시간복잡도 : O(n) [찾으려는 값이 없을 경우]
접근 - 배열의 인덱스로 데이터에 바로 접근할 수 있음 - 시간복잡도 : O(1)
추상 자료형 (ADT)
자료형
반환값
내용
initialize()
void
리스트 초기화
insert(Object data)
boolean
리스트에 데이터 저장
first()
Object
첫 번째 데이터를 가리키도록 하며 값을 반환
next()
Object
현재 참조하고 있는 데이터의 다음 데이터를 가리키도록 하며 값을 반환
remove()
Object
현재 참조하고 있는 데이터를 지움
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.ArrayList;
import List.List;
public class ArrayList implements List {
// 리스트 최대 개수를 10으로 지정
final int MAX_LIST_COUNT = 10;
Object[] list = new Object[MAX_LIST_COUNT];
// 현재 위치 저장 변수 (아무것도 참조하고 있지 않으므로 -1)
int curPosition = -1;
// 리스트에 저장된 데이터 개수
int countOfData = 0;
@Override
public void initialize() {
curPosition = -1;
countOfData = 0;
for(int i=0; i<MAX_LIST_COUNT; i++){
list[i] = null;
}
}
@Override
public boolean insert(Object data) {
if (data == null){
System.out.println("null 값을 추가할 수 없습니다.");
return false;
}
if (countOfData >= 100){
System.out.println("더이상 데이터를 추가할 수 없습니다.");
return false;
}
// 리스트에 데이터 저장
list[countOfData++] = data;
return true;
}
@Override
public Object first() {
if (countOfData == 0){
System.out.println("데이터가 없습니다.");
return null;
}
// 첫 번째를 가리키도록 설정
curPosition = 0;
// 첫 번째 데이터 반환
return list[curPosition];
}
@Override
public Object next() {
if (curPosition >= countOfData - 1){
System.out.println("데이터가 없습니다.");
return null;
}
curPosition++;
return list[curPosition];
}
@Override
public Object remove() {
if (countOfData == 0){
System.out.println("데이터가 없습니다.");
return null;
}
// 현재 참조된 데이터를 제거하기 위해 변수에 할당
Object rData = list[curPosition];
// 한 칸씩 당기기 위한 반복문
for(int i=curPosition; i<countOfData - 1; i++){
list[i] = list[i+1];
}
// 데이터가 제거됐으므로 개수와 위치를 하나씩 감소
countOfData--;
curPosition--;
return rData;
}
@Override
public int count() {
return countOfData;
}
}
메인 구현 데이터 삽입, 삭제 및 조회 기능 테스트
package List.ArrayList;
public class Main {
public static void main(String[] args) {
ArrayList list = new ArrayList();
// 리스트 초기화
list.initialize();
// 리스트 데이터 추가
list.insert(1); list.insert(2);
list.insert(3); list.insert(4);
list.insert(5); list.insert(6);
// 첫 번째 인덱스를 가리키도록 설정
Object data = list.first();
System.out.println(data);
// data가 null이 아닐때까지 반복
while((data = list.next()) != null){
System.out.println(data);
}
// data 삭제
Object rData = null;
data = list.first();
if ((int)data == 4){
rData = list.remove();
System.out.println(rData + " 데이터가 삭제되었습니다.");
rData = null;
}
while((data = list.next()) != null){
if ((int)data == 4){
rData = list.remove();
System.out.println(rData + " 데이터가 삭제되었습니다.");
rData = null;
}
}
// 삭제 후 재출력
data = list.first();
System.out.println(data);
// data가 null이 아닐때까지 반복
while((data = list.next()) != null){
System.out.println(data);
}
}
}
