'Algorithm&DataStructures/LinkedList&ArrayList'에 해당되는 글 4건

자바에서  이중 연결 리스트(DoublyLinkedList) - DoublyLinkedList in java

- 이중 연결 링스트의 장점은 단일 연결 리스트 보다 인덱스를 이용한 검색이 빠르다

-  단일 연결 리스트는 헤더에서 부터 검색을 하지만 이중연결 리스트는 양쪽에서 검색이 가능하다

- 단점은 구조가 복잡하며 메모리 소모가 단일 연결 리스트 보다는 있다

- 자바 콜렉션의 리스트는 이중 연결 리스트이다

1. DoubleLinkedList<E>.class

1) node.class

private class Node<E>{ private E data; private Node<E> pre; private Node<E> next; public Node(E data, Node pre, Node next){ this.data = data; this.pre = pre; this.next = next; } }

- 클래스 안의 중첩 클래스를 사용 하였다(가독성 좋다)

- pre 라는 변수가 추가 되었다(메모리 증가)

2) 정의

private Node<E> head; private Node<E> tail; private int size = 0;  

- size를 선언하여 보다 쉽게 제어가 가능하다

3) addFirst(E element)

public void addFirst(E element){ Node<E> newNode = new Node(element, head, null); if(head != null){ head.pre = newNode; } newNode.next = head; size++; head = newNode; if(head.next == null){ tail = head; } }  

- 앞에서 부터 요소를 추가 한다

4) addLast(E element)

public void addLast(E element){ Node<E> newNode = new Node(element, head, null); if(size == 0){ addFirst(element); }else{ tail.next = newNode; newNode.pre = tail; tail = newNode; size++; } }  

- 뒤에서 부터 요소 추가

5) node(int index)

public Node<E> node(int index){ if(index <= size/2){ Node<E> temp = head; for(int i = 0; i<index; i++){ temp = temp.next; } return temp; }else{ Node<E> temp = tail; for(int i = size - 1; i > index; i--){ temp = temp.pre; } return temp; } }  

- 인덱스를 이용하여 특정 노드를 찾는다. 이를 이용하여 특정 위치의 삽입/삭제가 가능하다

- 인덱스 값을 2로 나누어 작은 값은 head에서 부터 찾고 큰 값은 tail 에서 부터 찾는다

6) add(int x, E element)

public void add(int x, E element){ Node<E> newNode = new Node(element,head,tail); if(x == 0){ addFirst(element); }else if(x == size){ addLast(element); }else{ Node<E> temp = node(x-1); Node<E> temp2 = temp.next; temp.next = newNode; newNode.next = temp2; if(temp2 != null){ temp2.pre = newNode; } newNode.pre = temp; size++; if(newNode.next == null){ tail = newNode; } } }

- 원하는 위치에 데이터를 삽입한다

- 가운데 삽입 하기 때문에 앞뒤로 연결을 해야 한다

7. deleteFirst()

public E deleteFirst()throws Exception{ if(isNullCheck()){ throw new Exception("List is empty"); }else{ Node<E> temp = head; head = temp.next; E returnObject = temp.data; temp = null; if(head != null){ head.pre = null; } size--; return returnObject; } }

- 앞의 데이터를 삭제한다

8. deleteLast()

public E deleteLast()throws Exception{ if(isNullCheck()){ throw new Exception("List is empty"); }else{ Node<E> temp = tail; E returnObject = temp.data; tail = temp.pre; temp = null; size--; if(tail != null){ tail.next = null; } return returnObject; } }

- 뒤의 데이터를 삭제한다

9. delete(int x)

public E delete(int x)throws Exception{ E returnObject = null; if(isNullCheck()){ throw new Exception("List is empty"); }else{ if(x == 0){ deleteFirst(); }else if(x == size - 1){ deleteLast(); }else{ Node<E> temp = node(x-1); Node<E> deleted = temp.next; returnObject = deleted.data; temp.next = deleted.next; deleted.next.pre = temp; deleted = null; size--; } return returnObject; } }

- 특정 인덱스의 데이터를 삭제한다

10. get(int x)

public E get(int x){ Node<E> temp = node(x); return temp.data; }

- 데이터를 가져온다

11. indexOf(E element)

public int indexOf(E element){ Node<E> temp = head; int index = 0; while(temp.data != element){ index++; temp = temp.next; if(temp == null){ index = -1; } } return index; }

- 요소가 있는지 검사한다

- 있다면 index번호를 반환하고 없으면 -1을 반환한다

12. isNullCheck(), toString()

public boolean isNullCheck(){ return (head == null); } public String toString(){ String str = "{"; Node<E> temp = head; if(temp != null){ while(temp.next != null){ str += temp.data +","; temp = temp.next; } str += temp.data; } return str + "}"; }

- 리스트의 값이 있는지 여부와 추가/삭제된 데이터를 확인 할 수 있는 함수

13. main()

public static void main(String[]args){ DoubleLinkedList<Integer> list = new DoubleLinkedList<>(); try{ list.addLast(5); list.addLast(6); list.addLast(7); list.addLast(8); System.out.println(list.get(1)); System.out.println(list.indexOf(8)); }catch(Exception e){ System.out.println(e.getMessage()); } System.out.println(list); }

 자바 구현 Dynamic ArrayList -Dynamic ArrayList in java

- ArrayList는 데이터를 가져올 때 LinkedList 보다 빠르다

- 데이터 추가/삭제시 비효율 적이다

- 자바 내장 ArrayList는 사이즈가 100으로 되어 있으며 100이상이 되면 자동으로 2배 씩 증가한다

1. ArrayList<E>.class

1) 초기화

private int size = 0; private E[] data = (E[]) new Object[2];

- size 를 선언하여 요소 접근/삭제/추가시 유용하게 사용

- 배열의 크기를 2으로 지정한다(동적으로 증가한다)

2) addLast(E element)

public boolean addLast(E element){ if(isArrayFull()){ increaseArray(); System.out.println("Increasing array"); } data[size] = element; size++; return true; }  

- 배열의 뒤에서 부터 추가

- 뒤에서 부터 추가 되기 때문에 배열의 요소들이 움직일 필요가 없다

3. add(int index, E element)

public boolean add(int index, E element){ if(isArrayFull()){ increaseArray(); System.out.println("Increasing array"); } for(int i = size - 1; i >= index; i--){ data[i+1] = data[i]; } data[index] = element; size++; return true; }  

- 배열의 특정 위치에 추가 한다

- 특정 위치에 추가 되기 때문에 배열 요소들을 뒤로 한 칸 씩 이동하는 작업이 필요하다

 - for문을 큰 번호 에서 작은 번호로 이동하며 움직인다, 이후에 공간을 확보 하고 삽입한다

4. addFirst(E element)

public boolean addFirst(E element){ add(0, element); return true; }  

- 첫 번째 삽입 되면 배열 요소의 재배치가 필요하다

- add() 이용

5. remove(int index)

public E remove(int index){ E dataRemoved = data[index]; for(int i = index; i < size -1 ; i++){ data[i] = data[i+1]; } size--; return dataRemoved; }  

- 특정 인덱스의 값을 삭제한다

- 배열의 재배치가 일어난다, 앞으로 이동해야 하기 때문에 작은 번호 부터 큰 번호 까지 for문을 동작

6. removeFirst()/removeLast()

public E removeFirst(){ return remove(0); } public E removeLast(){ return remove(size - 1); }  

- remove() 이용

7. get(int index)

public E get(int index){ return data[index]; }  

- 데이터를 가져온다

8. indexOf(E element)

public int indexOf(E element){ int index = 0; for(int i = 0; i<size; i++){ if(data[i].equals(element)){ index = i; } } return index; }  

- 특정 데이터가 있는지 탐색한다

- 데이터가 있다면 데이터 위치를 나타내는 index 번호를 반환한다

9. isFullArray()/ increaseArry()

public void increaseArray(){ E[] newArry = (E[]) new Object[data.length * 2]; for(int i = 0; i<size; i++){ newArry[i] = data[i]; } data = newArry; } public boolean isArrayFull(){ return(size == data.length); }  

- 배열이 가득  차 있는지를 체크한다

- 동적으로 배열의 크기를 늘린다

10. toString()

public String toString(){ String str = "["; for(int i = 0; i<size; i++){ str += data[i]; if(i != size-1){ str += ","; } } str += "]"; return str; }  

- 상태 확인을 위한 출력 함수

2. Main.class

public static void main(String[]args){ ArrayList<Integer> list = new ArrayList<>(); list.addLast(1); list.addLast(2); System.out.println(list); list.addFirst(10); list.addFirst(20); System.out.println(list); list.add(2, 100); list.add(0, 200); list.addLast(300); list.addLast(400); System.out.println(list); list.addLast(500); System.out.println(list); list.remove(1); System.out.println(list); list.removeFirst(); list.removeLast(); System.out.println(list); System.out.println(list.get(3)); System.out.println(list.indexOf(100)); }  

 자바에서 ArrayList - Inner-ArrayList in java

- 자바에서 자체적으로 ArrayList 콜렉션을 지원한다

1. 구현

public class InnerArrayList { public static void main(String[] args){ ArrayList<Integer> list = new ArrayList<>(); //추가 list.add(1); list.add(2); list.add(3); list.add(4); System.out.println(list); //특정 위치 추가 list.add(1,6); System.out.println(list); //삭제 list.remove(2); System.out.println(list); //가져오기 System.out.println(list.get(3)); //탐색(iterator) Iterator it = list.iterator(); while(it.hasNext()){ int value = (int)it.next(); if(value == 3){ it.remove(); } } System.out.println(list); //탐색(for each) for(int value : list){ System.out.println(value); } //탐색(for) for(int i = 0 ; i<list.size(); i++){ System.out.println(list.get(i)); } } }

링크드리스트(LinkedList) -단방향 링크드 리스트(Singly Linked List)

- 링크드 리스트는 데이터 추가 삭제시에 효율적이다

- 메모리가 허용되는 한 계속 추가 할 수 있다

1. Node<T>.class

class Node<T> { private Node<T> nextRef; private T value; public void setValue(T value){ this.value = value; } public T getValue(){ return value; } public void setNextRef(Node<T> nextRef){ this.nextRef = nextRef; } public Node<T> getNextRef(){ return nextRef; } }

- 위에 있는 data/next의 한 블록을 노드라고 한다

- 링크드 리스트를 구현하기 위해선 노드가 필요하다

- data는 노드의 값이면 next는 다음 노드를 가르키기 위한 주소 값이 들어간다

2. SingleLinkedList<T>.class

1) 변수 정의

private Node<T> head; private Node<T> tail; private int size = 0;  

- head, tail 객체를 선언한다. head와 tail은 노드의 추가 삭제시의 참고가 된다

- head, tail은 하나의 노드라기 보다는 노드들을 컨트롤 할 수 있는 설명서의 역할

- size는 엘리먼트의 크기를 나타 낸다

2) addLast(T element)

public void addLast(T element){ Node<T> newNode = new Node<T>(); newNode.setValue(element); System.out.println("adding:"+element); size++; if(head == null){ head = newNode; tail = newNode; }else{ //이 부분은 결국 앞 노드의 다음 노드를 가르키는 부분을 셋팅 하는 것과 같다 tail.setNextRef(newNode); tail = newNode; } }  

- 노드를 뒤에서 추가한다

- 노드가 없을 시에 처음 head와 tail은 모두 처음 추가된 노드를 가르키게 된다

- 이후에 추가된 노드는 tail 값을 참조하여 추가한다

- 처음 추가된 노드가 얕은 복사(shallow copy) 과정이 일어나서 tail의 next값을 셋팅 하더라도 앞 노드의 다음 주소값을 셋팅 하는 효과가 일어난다

3) addFirst(T element)

public void addFirst(T element){ Node<T> newNode = new Node<>(); newNode.setValue(element); newNode.setNextRef(head); head = newNode; size++; //처음 노드 일 때 if(head.getNextRef() == null){ tail = newNode; } }  

- head의 값을 참조 하여 앞에 노드를 추가한다

- 처음 노드가 추가 되는 거라면 tail을 새로운 노드로 지정

4) node(int x)

public Node<T> node(int x){ Node<T> temp = head; //인덱스 값을 바탕으로 탐색을 시작 for(int i = 0; i<x; i++){ temp = temp.getNextRef(); } return temp; }  

- 특정 노드의 위치를 찾는 함수이다

- 이 함수를 이용하여 특정위치 추가/삭제 또는 데이터 가져오기가 가능하다

- head를 시작으로 계속 다음 노드 값을 추적하여 최종 인덱스 의 값을 찾는다

5) add(T element, int x)

public void add(T element,int index){ Node<T> newNode = new Node<>(); newNode.setValue(element); if(size == index + 1){ addLast(element); }else if(index == 0){ addFirst(element); }else{ Node<T> temp = node(index-1); newNode.setNextRef(temp.getNextRef()); temp.setNextRef(newNode); size++; if(newNode.getNextRef() == null){ tail = newNode; } } }  

- 특정 위치에 노드를 삽입한다

- index - 1은 원하는 위치의 값은 바로 그 뒤의 노드가 알기 때문에 바로뒤의 노드를 이용하여 삽입한다

6) deleteFirst()

public Node<T> deleteFirst(){ Node<T> returnData = head; head = returnData.getNextRef(); System.out.println("deleteFirst:"+returnData.getValue()); size--; return returnData; }  

- 앞의 노드 삭제

- head를 앞의 노드가 가르키는 값으로 지정한다

7) delete(int T)

public Node<T> delete(int element){ if(element == 0){ return deleteFirst(); } Node<T> temp = node(element-1); Node<T> deletedData = temp.getNextRef(); temp.setNextRef(temp.getNextRef().getNextRef()); size--; if(deletedData == tail){ tail = temp; } System.out.println("delete:" +deletedData.getValue()); return deletedData; }  

- 특정 위치의 노드를 삭제한다

- node()를 이용하여 위치를 찾고 사이의 연결 고리를 이어준다

8) deleteLast()

public Node<T> deleteLast(){ return delete(size-1); }  

- 마지막 노드 삭제

9) toString()

public String toString(){ if(head == null){ return "[]"; } Node<T> temp = head; String str = "["; while(temp.getNextRef() != null){ str += temp.getValue() + ","; temp = temp.getNextRef(); } str += temp.getValue(); return str+"]"; }  

- 요소의 상태를 알 수 있도록 화면에 출력한다

10) get()

public T get(int x){ Node<T> temp = node(x); return temp.getValue(); }  

- 요소 값 가져오기

11) main()

public static void main(String[]args){ SingleLinkedList<Integer> node = new SingleLinkedList(); node.addLast(1); System.out.println(node); node.addLast(2); System.out.println(node); node.addLast(3); System.out.println(node); node.addFirst(9); System.out.println(node); node.addFirst(10); System.out.println(node); node.deleteLast(); System.out.println(node); node.deleteLast(); System.out.println(node); node.add(99, 1); System.out.println(node); node.add(100, 3); System.out.println(node); node.add(1000, 0); System.out.println(node); System.out.println(node.get(2)); }