<List>
정의
: 순서가 있는 연속된 독립체들의 모음
예를 들면 (Y, M, D)는 (D, M, Y)와는 다릅니다.
기능
1. 처음과 끝 혹은 임의의 순서 i번째에 자료를 추가할 수 있습니다.
2. 처음과 끝 혹은 임의의 순서 i번째의 자료를 제거할 수 있습니다.
3. 처음과 끝 혹은 임의의 순서 i번째의 자료를 읽거나 변경할 수 있습니다.
배열(Array)과 리스트(List)의 차이점은 공백의 허용 여부입니다.
배열의 경우 중간에 데이터가 없어도 되지만, 리스트의 경우엔 빈 공간 없이 연속적으로 데이터가 등장해야 합니다.
리스트가 공백을 허용하지 않음으로써 얻는 이점은 저장 공간의 낭비가 없다는 것입니다.
리스트를 구현하는 방법에는 두 가지가 있습니다.
1. 기존에 있는 배열을 이용하여 만드는 방법
2. Linked List로 만드는 방법.
기존의 배열을 가지고 리스트를 만든다면 자료 조작 시 빈칸이 안 생기며, 자료의 손실이 없게 만들면 됩니다. 일단 방법 자체는 쉬우나 배열을 이용하기 때문에 그 크기가 유한하다는 단점이 있습니다.
Linked List로 구현하려면 일단 Linked List가 무엇인지 알아야 합니다.
Linked라는 말에서 알 수 있듯이 연결되어 있음을 말합니다.
List에서 자료를 가지고 있는 하나하나의 단위를 node라고 하고, 이 각각의 노드가 바로 다음에 올 node를 가리키고 있을 때 Linked List라고 합니다.
위의 그림에 나온 Linked List는 바로 뒤의 node만을 가리키고 있는 단일 Linked List(Singly Linked List)이며, 만약 전 후의 node를 가리키고 있다면 이중 Linked List(Doubly Linked List)라고 할 수 있습니다.
이외에도 맨 마지막 노드(tail)가 맨 앞의 node(header)를 가리키고 있다면 순환적인 구조로 아래와 같은 모양 일 것입니다.
모습이 원형을 띄고 있어 원형 리스트 (Circular List)라는 종류도 있습니다.
JAVA Code
1. Array Based List
ArrayBasedList.java
package lists;
import java.util.Scanner;
public class ArrayBasedList {
private int arr[];
private int maxSize = 0;
private int currSize = 0;
// ArrayBasedList의 생성자로 최대 크기제한을 인자로 받습니다.
public ArrayBasedList(int arrSize) {
maxSize = arrSize;
arr = new int[maxSize];
initList();
}
// ArrayBasedList의 초기화 함수로 최대 크기의 절반까지 index에 맞는 숫자를 data로 갖습니다.
public void initList() {
for(int i = 0; i < maxSize/2 ; i++) {
arr[i] = i;
}
currSize = maxSize/2;
}
// 자료를 추가하는 함수로 인덱스와 넣을 자료값을 인자로 받습니다. 해당 index에 기존에 있던 자료들 부터 마지막 자료까지 한칸씩 뒤로 이동시키며, 이동을 마친 후 data를 넣습니다.
public void addData(int index, int data) {
if(currSize == 0) {
System.out.println("현재 자료의 수가 0개 이기에, 0번째 Index에 자료를 추가합니다.");
arr[0] = data;
currSize++;
System.out.println("해당 작업의 수행결과, 아래와 같이 List가 변경되었습니다.");
printList();
} else if(index < 0) {
System.out.println("index가 주어진 조건에 맞지 않습니다.");
System.out.println("0에서 " + currSize + "사이의 수를 입력해주세요");
} else if(index > currSize){
System.out.println("주어진 index가 현재 리스트 크기보다 크므로, 가장 마지막에 자료를 입력하겠습니다.");
arr[currSize] = data;
System.out.println("해당 자료 " + data + "는 " + currSize + " index 자리에 저장되었습니다.");
currSize++;
System.out.println("해당 작업의 수행결과, 아래와 같이 List가 변경되었습니다.");
printList();
} else {
for(int i = currSize; i > index; i--) {
arr[i] = arr[i-1];
}
arr[index] = data;
currSize++;
System.out.println("해당 작업의 수행결과, 아래와 같이 List가 변경되었습니다.");
printList();
}
}
// 자료를 삭제하는 함수로 인덱스를 인자로 받습니다. 해당 index 이후에 있는 자료들을 각각 한칸씩 앞으로 땡겨와 자료를 덮어씁니다. 가장 마지막 데이터는 지워졌음을 표시하기 위해서 -9999를 넣어 주었습니다.
public void deleteData(int index) {
if(currSize == 0) {
System.out.println("There is no data!");
} else if(index >= currSize || index < 0){
System.out.println("입력한 Index가 조건에 맞지 않습니다.");
System.out.println("0에서 " + (currSize-1) + "까지의 수를 입력해 주세요." );
} else {
for(int i = index; i < currSize; i++) {
arr[i] = arr[i+1];
}
arr[currSize] = -9999;
currSize--;
System.out.println("해당 작업의 수행결과, 아래와 같이 List가 변경되었습니다.");
printList();
}
}
// 자료를 수정하는 함수 입니다. 인덱스와 데이터를 인자로 받아와 해당 인덱스의 데이터를 바꿉니다.ㅏ
public void changeData(int index, int data) {
if(index < 0 || index >=currSize) {
System.out.println("입력한 Index가 조건에 맞지 않습니다.");
System.out.println("0에서 " + (currSize-1) + "까지의 수를 입력해 주세요." );
} else {
arr[index] = data;
System.out.println("해당 작업의 수행결과, 아래와 같이 List가 변경되었습니다.");
printList();
}
}
// 자료를 읽어오는 함수 입니다. 인덱스를 인자로 받아와 해당 인덱스의 데이터를 출력합니다.
public void readData(int index) {
if(index < 0 || index >=currSize) {
System.out.println("입력한 Index가 조건에 맞지 않습니다.");
System.out.println("0에서 " + (currSize-1) + "까지의 수를 입력해 주세요." );
} else {
System.out.println("입력한 Index에 해당하는 자료는 " + arr[index] + "입니다.");
}
}
// 자료가 저장된 List를 출력하는 함수 입니다. 현재 자료의 수만큼 반복문을 진행시켜 출력합니다.
public void printList() {
System.out.println();
System.out.println("*ArrayBased List*");
System.out.println("List Maximum Size :" + maxSize);
System.out.println("List Currnet Data Figure :" + currSize);
for(int i = 0; i < currSize; i++) {
System.out.println(i + "번째 자료 : " + arr[i]);
}
}
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
boolean loopCondition = true;
String work = new String();
int maxSize, index, data;
System.out.print("List의 최대 크기를 입력해 주세요(양의 정수):");
maxSize = scanner.nextInt();
ArrayBasedList arrList = new ArrayBasedList(maxSize);
// loopCondition이 false가 되기 전까지 작업을 계속 진행합니다.
while(loopCondition) {
System.out.print("작업을 입력해주세요 (add/delete/change/read/print/exit): ");
work = scanner.next();
switch(work) {
case "add" :
System.out.print("추가하길 원하는 위치를 입력해주세요:");
index = scanner.nextInt();
System.out.print("추가하길 원하는 자료를 입력해주세요:");
data = scanner.nextInt();
arrList.addData(index, data);
break;
case "delete":
System.out.print("제거하길 원하는 위치를 입력해주세요:");
index = scanner.nextInt();
arrList.deleteData(index);
break;
case "change":
System.out.print("변경하길 원하는 위치를 입력해주세요:");
index = scanner.nextInt();
System.out.print("변경할 자료를 입력해주세요:");
data = scanner.nextInt();
arrList.changeData(index, data);
break;
case "read":
System.out.print("확인하길 원하는 위치를 입력해주세요:");
index = scanner.nextInt();
arrList.readData(index);
break;
case "print":
arrList.printList();
break;
case "exit":
loopCondition = false;
System.out.println("사용을 종료합니다.");
break;
default :
System.out.print("잘못 입력하셨습니다. 다시 입력해주세요.");
}
System.out.println();
}
scanner.close();
}
}
2. Linked List
Node.java
package lists;
public class Node {
private int data = 9999;
private Node preNode = null;
private Node afterNode = null;
public Node() {
}
// Node의 생성자로, data와 이전 Node, 이후 Node를 인자로 받습니다.
public Node(int data, Node preNode, Node afterNode) {
this.data = data;
this.preNode = preNode;
this.afterNode = afterNode;
}
public int getData() {
return data;
}
public void setData(int data) {
this.data = data;
}
public Node getPreNode() {
return preNode;
}
public void setPreNode(Node preNode) {
this.preNode = preNode;
}
public Node getAfterNode() {
return afterNode;
}
public void setAfterNode(Node afterNode) {
this.afterNode = afterNode;
}
}
LinkedList.java
package lists;
import java.util.Scanner;
public class LinkedList {
private Node header;
private Node tail;
// Linked List의 생성자로 header와 tail을 생성해서 서로를 연결시켜줍니다.
public LinkedList() {
header = new Node(0, null, null);
tail = new Node (-9999, header, null);
header.setAfterNode(tail);
}
// 자료를 추가하는 메서드입니다. 자료 값과 인덱스를 인자로 받습니다. 주어진 인덱스가 전체 리스트의 절반 이하라면 header부터 탐색하고, 초과라면 tail부터 탐색합니다. 탐색이 완료되면 자료 값을 담은 새로운 Node를 만들고 해당 인덱스에 존재하던 Node를 이후 노드로 추가하고 다른 Node들의 연결 또한 조절합니다.
public void addNode(int data, int index) {
int currSize = header.getData();
int count = 0;
Node currNode = null;
Node preNode = null;
if(currSize == 0) {
System.out.println("현재 자료의 수가 0개 이기에, 1번째 Index에 자료를 추가합니다.");
Node tempNode = new Node(data, header, tail);
header.setAfterNode(tempNode);
tail.setPreNode(tempNode);
header.setData(currSize + 1);
System.out.println("해당 작업의 수행결과, 아래와 같이 List가 변경되었습니다.");
printList();
} else if(index < 1 || index > currSize + 1) {
System.out.println("index가 주어진 조건에 맞지 않습니다.");
System.out.println("1에서 " + (currSize + 1) + "사이의 수를 입력해주세요");
}else {
if(index <= currSize/2 + 1) {
currNode = header;
while(count != index) {
currNode = currNode.getAfterNode();
count++;
}
}else {
currNode = tail;
while(currSize + 1 - count != index) {
currNode = currNode.getPreNode();
count++;
}
}
preNode = currNode.getPreNode();
Node tempNode = new Node(data, preNode, currNode);
preNode.setAfterNode(tempNode);
currNode.setPreNode(tempNode);
header.setData(currSize + 1);
System.out.println("해당 작업의 수행결과, 아래와 같이 List가 변경되었습니다.");
printList();
}
}
// 자료를 지우는 메서드로 인덱스를 인자로 받습니다. addNode에서 했던 것과 마찬가지로 현재 Node를 탐색하고 해당 데이터의 전 후 Node들을 서로 연결 시켜 주고 현재 노드를 없애줍니다.
public void deleteNode(int index) {
int currSize = header.getData();
int count = 0;
Node currNode = null;
Node preNode = null;
Node afterNode = null;
if(currSize == 0) {
System.out.println("There is no data!");
} else if(index > currSize || index < 1){
System.out.println("입력한 Index가 조건에 맞지 않습니다.");
System.out.println("1에서 " + currSize + "까지의 수를 입력해 주세요." );
} else {
if(index <= currSize/2 + 1) {
currNode = header;
while(count != index) {
currNode = currNode.getAfterNode();
count++;
}
preNode = currNode.getPreNode();
afterNode = currNode.getAfterNode();
preNode.setAfterNode(afterNode);
afterNode.setPreNode(preNode);
currNode = null;
header.setData(currSize-1);
}else {
currNode = tail;
while(currSize + 1 - count != index) {
currNode = currNode.getPreNode();
count++;
}
preNode = currNode.getPreNode();
afterNode = currNode.getAfterNode();
preNode.setAfterNode(afterNode);
afterNode.setPreNode(preNode);
currNode = null;
header.setData(currSize-1);
}
System.out.println("해당 작업의 수행결과, 아래와 같이 List가 변경되었습니다.");
printList();
}
}
// 자료를 조회하는 메서드로 인덱스를 인자로 받아와 해당 인덱스를 가진 Node를 탐색하여 자료 값을 출력합니다.
public void readNode(int index) {
int currSize = header.getData();
int count = 0;
Node currNode = null;
if(currSize == 0) {
System.out.println("There is no data!");
} else if(index > currSize || index < 1){
System.out.println("입력한 Index가 조건에 맞지 않습니다.");
System.out.println("1에서 " + currSize + "까지의 수를 입력해 주세요." );
} else {
if(index <= currSize/2 + 1) {
currNode = header;
while(count != index) {
currNode = currNode.getAfterNode();
count++;
}
}else {
currNode = tail;
while(currSize + 1 - count != index) {
currNode = currNode.getPreNode();
count++;
}
}
System.out.println(index + "번째 데이터는 " + currNode.getData() + "입니다.");
}
}
// 자료를 변경하는 메서드로 자료 값과 인덱스를 인자로 받아와 해당 인덱스의 Node를 탐색하고 해당 Node의 자료 값을 수정합니다.
public void changeNode(int data, int index) {
int currSize = header.getData();
int count = 0;
int predata;
Node currNode = null;
if(currSize == 0) {
System.out.println("There is no data!");
} else if(index > currSize || index < 1){
System.out.println("입력한 Index가 조건에 맞지 않습니다.");
System.out.println("1에서 " + currSize + "까지의 수를 입력해 주세요." );
} else {
if(index <= currSize/2 + 1) {
currNode = header;
while(count != index) {
currNode = currNode.getAfterNode();
count++;
}
predata = currNode.getData();
currNode.setData(data);
}else {
currNode = tail;
while(currSize + 1 - count != index) {
currNode = currNode.getPreNode();
count++;
}
predata = currNode.getData();
currNode.setData(data);
}
System.out.println(index + "번째 데이터는 " + predata + "에서" + currNode.getData() + "로 변경되었습니다.");
}
}
// 자료가 저장된 리스트를 출력하는 메서드 입니다. 다음에 노드가 존재하지 않을 때 까지 출력을 진행합니다.
public void printList() {
int index = 0;
int currSize = header.getData();
Node tempNode = header;
System.out.println("------Linked List------");
while(tempNode.getAfterNode() != null) {
if(index == 0) {
System.out.println("List에 존재하는 자료의 수는 " + currSize + "개 입니다.");
}else {
System.out.println(index + "번째 데이터는 " + tempNode.getData());
}
tempNode = tempNode.getAfterNode();
index++;
}
System.out.println("------------------------\n");
}
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
boolean loopCondition = true;
String work = new String();
int index, data;
System.out.println("Linked List를 생성합니다.\n0번째는 header, 1번째는 tail입니다.\n데이터는 header 와 tail 사이에서 조작됩니다.");
LinkedList linkedList = new LinkedList();
linkedList.printList();
while(loopCondition) {
System.out.print("작업을 입력해주세요 (add/delete/change/read/print/exit): ");
work = scanner.next();
switch(work) {
case "add" :
System.out.print("추가하길 원하는 위치를 입력해주세요:");
index = scanner.nextInt();
System.out.print("추가하길 원하는 자료를 입력해주세요:");
data = scanner.nextInt();
linkedList.addNode(data, index);
break;
case "delete":
System.out.print("제거하길 원하는 위치를 입력해주세요:");
index = scanner.nextInt();
linkedList.deleteNode(index);
break;
case "change":
System.out.print("변경하길 원하는 위치를 입력해주세요:");
index = scanner.nextInt();
System.out.print("변경할 자료를 입력해주세요:");
data = scanner.nextInt();
linkedList.changeNode(data, index);
break;
case "read":
System.out.print("확인하길 원하는 위치를 입력해주세요:");
index = scanner.nextInt();
linkedList.readNode(index);
break;
case "print":
linkedList.printList();
break;
case "exit":
loopCondition = false;
System.out.println("사용을 종료합니다.");
break;
default :
System.out.print("잘못 입력하셨습니다. 다시 입력해주세요.");
}
System.out.println();
}
scanner.close();
}
}
'Computer Science(학업내용 정리) > 자료구조' 카테고리의 다른 글
| 자료구조 - 자료구조와 알고리즘 (0) | 2020.04.03 |
|---|
