[study] 2017-04-16 더블링크드리스트

자바에서  이중 연결 리스트(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, null, 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. size()

public int size(){ Node<T> temp = head; int count =0; if(temp != null){ while(temp.next != null){ count++; temp = temp.next; } if(temp.next != null){ count++; } } return count; }

14. clear()

public void clear(){ Node<T> temp = head; if(temp != null){ while(temp.next != null){ temp = temp.next; temp.pre.data = null; temp.pre.next = null; temp.pre = null; } temp.data = null; size = 0; } }

14. 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); }