LinkedList - 1

기초가 부족하단 생각에 자료구조부터 공부해보기로 했다

스프링, 익스프레스, 마이바티스 등등 프레임워크를 공부하면 할수록
기초가 중요하다는 생각이 들어 알고리즘, 자료구조등을 함께 공부하기로 했다.
먼저 자료구조중에 LickedList를 먼저 공부하려고 한다.

LinkedList

LinkedList란 하나의 노드에 데이터를 담고 다음 노드의 주소를 가르키는 자료구조이다.
다음 노드만 가리키는 Singly Linked List와
이전의 노드도 함께 양방향으로 가리키는 Doubly linked list가 있다.

LinkedList는 ArrayList에 비해 장단점이 있는데,
단점으론 현재 내 노드에서 곧바로 떨어진 노드로 갈 수 없다.
즉, 순차접근만이 가능해서 조회하는 일에는 적합하지 않다.

장점은 데이터를 삽입하거나 삭제하는 경우 노드들의 주소만 변경하면 되기 때문에
상대적으로 간단하게 삽입/삭제 할 수 있다.
또한 메모리상 붙어있지 않고 주소를 연결하기 때문에 개수의 한계가 없다.

구현

Doubly linked list를 간단하게 구현해보려고 한다.
java의 LinkedList와 생활코딩과를 참고했다.
이편에선 데이터 삽입만 구현한다.

[Doubly linked list] []

public class LinkedList<E> {
	//리스트의 사이즈와 처음노드과 마지막노드
	private int size;
	private Node<E> head;
	private Node<E> tail;
	
	//Node 클래스
	//Node는 제네릭을 사용하여 받는 타입을 외부에서 설정하게 한다 
	public static class Node<E> {
		E item;
		Node<E> next;
		Node<E> prev;

		public Node(Node<E> prev, E element, Node<E> next) {
			this.item = element;
			this.next = next;
			this.prev = prev;
		}
		
	}
	
	//데이터를 앞에 넣을때
	//새로 노드를 추가하고 head를 변경한다.
	//새로운 노드엔 다음 요소로 이전의 헤드를 지정한다.(없을시 null이 들어감)
	//이전 헤드가 없으면 요소가 1개로 tail과 head를 일치시킨다.
	//아니라면 이전 헤드의 이전 요소로 추가한 노드를 지정한다.
	public void addFirst (E element) {
		final Node<E> prevHead = head;
		
		Node<E> newNode = new Node<E>(null, element, head);
		head = newNode;
		
		if(prevHead == null) tail = head;
		else prevHead.prev = newNode;
		
		size++;
	}
	
	//데이터를 뒤에 넣을때
	//앞에 넣는 과정의 반대로 실행한다.
	public void addLast (E element) {
		final Node<E> prevTail = tail;
		
		Node<E> newNode = new Node<E>(tail, element, null);
		tail = newNode;
		
		if(prevTail == null) head = tail;
		else prevTail.next = newNode;
		
		size++;
	}
	
	//위치로 노드를 구할때
	//시작을 현재 헤드로 잡고
	//받은 인덱스만큼 순차적으로 다음 요소를 탐색하고
	//인덱스에 다다르면 요소를 반환한다.
	//양방향이기 때문에 인덱스를 사이즈를 반으로 나눈 값과 비교해
	//작으면 앞에서부터 찾고 크면 뒤에서부터 찾는다.  
	public Node<E> node(int index) {
		if(index < (size >> 1)){
		    Node<E> x = this.head; 
		    for(int i = 0; i < index; i++) {
			    x = x.next;
		    }
			return x;            
		} else {
		    Node<E> x = this.tail; 
		    for(int i = size - 1; i > index; i--) {
			    x = x.prev;
		    }
			return x;
		}
	}
	
	//노드를 중간에 삽입할때
	public void add(int index, E element) {
		Node<E> prev = node(index);
		Node<E> next = node(index+1);
		Node<E> newNode = new Node<E>(prev, element, next);
		prev.next = newNode; 
		next.prev = newNode;
		size++;
	}
	
	//결과를 출력
	public String toString() {
		if(head == null){
		        return "[]";
		}       
		 
		StringBuffer sb = 
		    new StringBuffer("[" + String.valueOf(this.head.item));
		    
		for (Node<E> x = this.head.next; x != null; x = x.next) {
			sb.append("," + String.valueOf(x.item));
                }
		 
	        return sb.append("]").toString();
	}
}	

출력테스트

[Doubly linked list] []

public static void main(String[]args) {
	LinkedList<Integer> list = new LinkedList<Integer>();
	list.addFirst(1);
	list.addFirst(2);
	list.addFirst(3);
	list.addFirst(4);
	list.add(2,8);
	System.out.println(list.toString());
}

출력결과

[Doubly linked list] []

[4,3,2,8,1]

2번으로 이어짐