[Java] 리스트

데이터를 순서대로 나열한 자료구조

(삽입 연산, 탐색 연산, 삭제 연산)

연결리스트

물리적으로 흩어져 있는 자료들을 서로 연결하여 하나로 묶는 방법
노드와 포인터로 구현한다.

노드 : 메모리의 어떤 위치에나 있을 수 있으며 다른 노드로 가기 위해서는 현재 노드가 가지고 있는 포인터를 이용하며 데이터 필드와 링크 필드로 구성되어 있다.

데이터 필드 : 저장할 데이터를 가진다.

링크 필드 : 다른 노드를 가리키는 포인터가 저장된다.

연결리스트의 장단점

장점 : 크기가 제한되지 않고, 중간에서 쉽게 삽입하거나 삭제할 수 있는 유연한 리스트 구현이 가능하다.
데이터를 저장할 공간이 필요할 때마다 동적으로 공간을 만들어서 쉽게 추가 가능하다.
단점 : 구현이 복잡하며 임의의 항목(i번째 항목)을 추출하려고 할 때 배열을 사용하는 방법보다 시간이 많이 걸린다.
데이터와 포인터를 저장해야 하므로 메모리 공간을 많이 사용한다.

연결리스트의 종류

단순 연결 리스트 : 하나의 방향으로만 연결되어 있는 연결 리스트이다. 체인(chain)이라고도 하며 마지막 노드의 링크는 NULL값을 가진다.
원현 연결 리스트 : 단순 연결 리스트와 동일하며 단, 마지막 노드의 링크가 첫 번째 노드를 가리킨다.
이중 연결 리스트 : 각 노드마다 2개의 링크가 존재하며 하나의 링크는 앞에 있는 노드를 다른 하나의 링크는 뒤에 있는 노드를 가리킨다.

포인터로 연결 리스트 만들기

LinkedList.java

• 노드 생성

	class Node<E> {
		private E data;
		private Node<E> next;

		// 노드 생성자
		Node(E data, Node<E> next) {
			this.data = data;
			this.next = next;
		}
	}

	private Node<E> head; // 머리 노드
	private Node<E> crnt; // 선택 노드

	// LinkedList<E>의 생성자
	public LinkedList() {
		head = crnt = null;
	}

• 삽입
  꼬리노드에 노드를 삽입하는 addLast메서드
  리스트가 비어있는 경우 즉, head==null일 경우 addFirst메서드를 사용하여
  노드를 삽입한다. 그렇지 않은 경우 ptr에 head를 삽입 후에 while문을 사용하여 리스트의 꼬리로 이동시킨 후 삽입할 노드를
  생성하고 선택 노드로 설정한다.

	public void addFirst(E obj) {
		Node<E> ptr = head;
		head = crnt = new Node<E>(obj, ptr);
	}
   	public void addLast(E obj) {
		if (head == null)
			addFirst(obj);
		else {
			Node<E> ptr = head;
			while (ptr != null)
				ptr = ptr.next;
			ptr.next = crnt = new Node<E>(obj, null);
		}
	}

• 탐색
  검색을 수행하는 search 메서드
  obj : 검색할 때 key가 되는 데이터를 가지는 object
  c : 첫 번째 매개변수와 연결
  리스트의 개별 노드 안에 있는 데이터를 비교하기 위한 comparator 매개 변수 comparator c 에 의해 obj와 선택한 노드의
  데이터를 비교하여 그 결과가 0이면 검색 조건이 성립하는것으로 본다

	public E search(E obj, Comparator<? super E> c) {
		Node<E> ptr = head; // 첫번째 노드부터 탐색

		while (ptr != null) {
			if (c.compare(obj, ptr.data) == 0) { // 검색 성공
				crnt = ptr;
				return ptr.data;
			}
			ptr = ptr.next; // 다음 노드 선택
		}
		return null; // ptr이 비어있다면 null이라면 검색 실패
	}

• 삭제
  선택한 노드를 삭제하는 remove()메서드
  리스트가 비지 않은 상태에서 선택한 노드를 p라고 하고 p가 head이면 removeFirst()메서드를 사용하여 삭제한다.
  그 외의 경우에는 ptr을 사용하여 ptr.next가 p가 될때까지 탐색하고 p가 나오지 않고 ptr이 null이 되면 return 을 사용하여 메서드를 끝낸다.(리스트 내에 p라는 노드 존재 안하는 경우이다)
  ptr.next가 p가 되면 ptr이 p.next를 가리키도록하여 p를 어디에서도 참조 하지 않도록 하여 노드 p를 삭제한다.

	public void remove(Node<E> p) {
		if(head!=null) {
			if(p==head)
				removeFirst();
			else {
				Node<E> ptr=head;
				
				while(ptr.next!=p) { 
					ptr=ptr.next;
					if(ptr==null) return; //p가 리스트에 없는 경우
				}
				ptr.next=p.next;
				crnt=ptr;
			}
		}
	}

Runner 기법

연결리스트를 순회할 때 두 개의 포인터를 동시에 사용하는 기법이다. 이때 한 포인터가 다른 포인터보다 앞서도록 한다. 앞선 포인터가 따라오는 포인터보다 항상 지정된 개수만큼을 앞서도록 할 수도 있고, 아니면 따라오는 포인터를 여러 노드를 한 번에 뛰어넘도록 설정할 수도 있다.

다음 코드 참고
꼬리노드를 삭제하는 removeLast() 메서드
리스트가 비어있지 않은 상태에서 만약 노드가 1개 뿐이라면 removeFirst()메서드를 사용하여 삭제하고
그렇지 않다면 꼬리노드를 탐색할 ptr과 ptr바로 앞의 노드를 가리킬 pre를 생성하고 꼬리노드를 찾으면
꼬리노드 앞의 노드인 pre의 다음 노드 pre.next가 null을 가리키도록 설정하여
pre를 꼬리 노드로 설정한다.

	public void removeLast() {
		if (head != null) {
			if (head.next == null)
				removeFirst();
			else {
				Node<E> ptr = head;
				Node<E> pre = head;

				while (ptr != null) {
					pre = ptr;
					ptr = ptr.next;
				}
				pre.next = null;
				crnt = pre;
			}
		}
	}