코딩 기록들
Java 2. 배열(Array), 연결리스트(Linked list) 구현 본문
Array
- 동일한 데이터 타입을 순서에 따라 관리하는 자료 구조
- 정해진 크기가 있음
- 요소의 추가와 제거시 다른 요소들의 이동이 필요함
- 배열의 i 번째 요소를 찾는 인덱스 연산이 빠름
- jdk 클래스 : ArrayList(오프벡트 클래스로 되어있음), Vector
public class MyArray {
int[] intArr; //int array
int count; //개수
public int ARRAY_SIZE;
public static final int ERROR_NUM = -999999999;
public MyArray()
{
count = 0;
ARRAY_SIZE = 10;
intArr = new int[ARRAY_SIZE];
}
public MyArray(int size)
{
count = 0;
ARRAY_SIZE = size;
intArr = new int[size];
}
public void addElement(int num)
{
if(count >= ARRAY_SIZE){
System.out.println("not enough memory");
return;
}
intArr[count++] = num;
}
//배열의 중간에 들어오는 경우 구현
// 이동의 수는 요소의 개수에 비례함
public void insertElement(int position, int num) // 어디에(index값 position) 넣을거고, 데이터가 뭔지
{
int i;
if(count >= ARRAY_SIZE){ //이미 배열이 꽉 찬 경우
System.out.println("not enough memory");
return;
}
if(position < 0 || position > count ){ //index error : 0보다 작거나, 중간에 배열이 비어있을경우
System.out.println("insert Error");
return;
}
//실제적으로 이동하는 부분
for( i = count-1; i >= position ; i--){ //마지막요소부터 position값 위치까지
intArr[i+1] = intArr[i]; // 하나씩 뒤로 이동
}
intArr[position] = num; //내가 값을 넣을 위치는 position!
count++;
}
//배열에서 삭제하는 코드 구현
public int removeElement(int position)
{
int ret = ERROR_NUM;
if( isEmpty() ){ // 배열이 아예 비어있는 경우
System.out.println("There is no element");
return ret;
}
if(position < 0 || position >= count ){ //삭제하는것이 가능한것인지 판단(줄수있는 요소값이 없으므로 에러!) - index error
System.out.println("remove Error");
return ret;
}
ret = intArr[position];
for(int i = position; i<count -1; i++ )
{
intArr[i] = intArr[i+1];
}
count--;
return ret;
}
public int getSize()
{
return count;
}
public boolean isEmpty()
{
if(count == 0){
return true;
}
else return false;
}
public int getElement(int position)
{
if(position < 0 || position > count-1){
System.out.println("검색 위치 오류. 현재 리스트의 개수는 " + count +"개 입니다.");
return ERROR_NUM;
}
return intArr[position];
}
public void printAll()
{
if(count == 0){
System.out.println("출력할 내용이 없습니다.");
return;
}
for(int i=0; i<count; i++){
System.out.println(intArr[i]);
}
}
public void removeAll()
{
for(int i=0; i<count; i++){
intArr[i] = 0;
}
count = 0;
}
}
링크드리스트
- 요소를 추가하거나 삭제할경우 해당position 의 previous element 를 찾아야함
public class MyListNode {
private String data; // 자료
public MyListNode next; // 다음 노드를 가리키는 링크
public MyListNode(){ // 데이터가 없을경우 null로 생성
data = null;
next = null;
}
public MyListNode(String data){
this.data = data;
this.next = null; // 다음꺼 가리키는 값 : null
}
public MyListNode(String data, MyListNode link){
this.data = data;
this.next = link; // 다음꺼 가리키는 값 지정
}
public String getData(){
return data;
}
}
(삭제할때 예시)
//head-node가 맨 처음 엘리먼트를 가리키는 구조
public class MyLinkedList {
private MyListNode head; // 이 head가 첫번째 요소로 링크드리스트 구현
int count; //count = 개수 (링크드리스트에 몇개가 연결되어있는지)
public MyLinkedList()
{
head = null;
count = 0;
}
public MyListNode addElement( String data )
{
MyListNode newNode;
//맨앞에 들어가는 경우
if(head == null){ //맨 처음일때
newNode = new MyListNode(data);
head = newNode; //head가 첫번째 노드가 됨
}
//맨끝에 들어가는 경우
else{ //head가 첫번째 노드가 아닐경우
newNode = new MyListNode(data);
MyListNode temp = head; //맨 마지막 노드를 찾기위해 첫번째 element인 head부터 돈다
while(temp.next != null) //null이라는건, 다음요소가 없다는것. 즉, 맨마지막 요소라는것! 맨 뒤로 가서, 맨 마지막 노드가 null일 경우
temp = temp.next;
temp.next = newNode; //새로 들어가는요소는 기존의 젤 마지막요소 뒤에 위치하게됨
}
count++;
return newNode;
}
// 중간에 들어가는 경우
// -> previous를 찾아야함
public MyListNode insertElement(int position, String data )
{
int i; //포지션을 찾기 위함
MyListNode tempNode = head;
MyListNode preNode = null; //null로 초기화 잊지말고 할것
MyListNode newNode = new MyListNode(data);
if(position < 0 || position > count ){
System.out.println("추가 할 위치 오류 입니다. 현재 리스트의 개수는 " + count +"개 입니다.");
return null;
}
//맨앞에 요소추가
if(position == 0){ //맨 앞으로 들어가는 경우 : head가 됨
newNode.next = head; //원래 head였던것이 head 다음 요소가 되고
head = newNode; // 원래 head자리에 newNode값이 들어옴
}
//중간에 요소추가
else{
for(i=0; i<position; i++){ //previous노드의 위치 찾는용도
preNode = tempNode; //position보다 하나 작았을때로 preNode의 위치가 정해짐
tempNode = tempNode.next; //tempNode는 previous의 다음위치, 실제 들어갈 위치가 됨
}
newNode.next = preNode.next; //들어갈값의 next = previous가 가리키는 값
preNode.next = newNode;
}
count++;
return newNode;
}
//이전노드 찾아서 삭제
public MyListNode removeElement(int position)
{
int i;
MyListNode tempNode = head;
MyListNode preNode = null;
if(position >= count ){
System.out.println("삭제 할 위치 오류입니다. 현재 리스트의 개수는 " + count +"개 입니다.");
return null;
}
if(position == 0){ //맨 앞을 삭제하는
head = tempNode.next;
}
else{
for(i=0; i<position; i++){
preNode = tempNode;
tempNode = tempNode.next; // 지워지는 요소 = tempNode
}
preNode.next = tempNode.next; // pre는 temp의 next를 가리키게 된다
}
count--;
System.out.println(position + "번째 항목 삭제되었습니다.");
return tempNode; //return값 = 삭제되는 노드
}
public String getElement(int position)
{
int i;
MyListNode tempNode = head;
if(position >= count ){
System.out.println("검색 위치 오류 입니다. 현재 리스트의 개수는 " + count +"개 입니다.");
return new String("error");
}
if(position == 0){ //맨 인 경우
return head.getData();
}
for(i=0; i<position; i++){
tempNode = tempNode.next;
}
return tempNode.getData();
}
public MyListNode getNode(int position)
{
int i;
MyListNode tempNode = head;
if(position >= count ){
System.out.println("검색 위치 오류 입니다. 현재 리스트의 개수는 " + count +"개 입니다.");
return null;
}
if(position == 0){ //맨 인 경우
return head;
}
for(i=0; i<position; i++){
tempNode = tempNode.next;
}
return tempNode;
}
public void removeAll()
{
head = null;
count = 0;
}
public int getSize()
{
return count;
}
public void printAll()
{
if(count == 0){
System.out.println("출력할 내용이 없습니다.");
return;
}
MyListNode temp = head;
while(temp != null){
System.out.print(temp.getData());
temp = temp.next;
if(temp!=null){
System.out.print("->");
}
}
System.out.println("");
}
public boolean isEmpty()
{
if(head == null) return true;
else return false;
}
}public class MyLinkedListTest {
public static void main(String[] args) {
MyLinkedList list = new MyLinkedList();
list.addElement("A");
list.addElement("B");
list.addElement("C");
list.printAll();
list.insertElement(3, "D"); //여기서 3의위치 = 맨 뒤
list.printAll();
list.removeElement(0); //맨앞에있는 요소인 head를 지워라
list.printAll();
list.removeElement(1);
list.printAll();
list.insertElement(0, "A-1");
list.printAll();
System.out.println(list.getSize());
list.removeElement(0);
list.printAll();
System.out.println(list.getSize());
list.removeAll();
list.printAll();
list.addElement("A");
list.printAll();
System.out.println(list.getElement(0));
list.removeElement(0);
}
}