연결리스트(Linked List)

[ 연결리스트를 구성하는 기본 단위 "노드" ]

- 각각의 노드는 "데이터 필드"와 하나 혹은 그 이상의 "링크 필드"로 구성된다.

- 링크 필드는 다음 노드를 참조한다.

- 첫 번째 노드의 주소는 따로 저장해야 한다.

 

연결리스트의 구조는 아래와 같다.

MySingleLinkedList 클래스의 head 는 첫 번째 노드를 가리킨다. 그리고 각 노드의 링크 필드(next)는 다음 노드를 가리킨다. 현재 노드가 마지막 노드라면 링크 필드는 그냥 null 이다.

 

[ Node.class ]

public class Node<T> {
	// 데이터 필드와 , 링크 필드로 구성된다.
	public T data;
	public Node<T> next;

	public Node(T item) {
		data = item;
		next = null;
	}
}

[ MySingleLinkedList.class ]

package section7;

public class MySingleLinkedList<T> {

	// 첫 번째 노드의 주소
	public Node<T> head;
	public int size;

	public MySingleLinkedList() {
		head = null;
		size = 0;
	}

	public void addFrist(T item) {
		Node<T> fristNode = new Node<T>(item);

		fristNode.next = head;
		head = fristNode;
		size++;
	}

	public void addAfter(Node<T> before, T item) {
		Node<T> temp = new Node<T>(item);

		temp.next = before.next;
		before.next = temp;
		size++;
	}

	// index - 1 번째 노드 뒤에 추가된다.
	public void add(int index, T item) {
		if (index < 0 || index > size)
			return;

		if (index == 0) {
			addFrist(item);
		} else {
			Node<T> q = getNode(index - 1);
			addAfter(q, item);
		}

	}

	public T remove(int index) {
		if (index < 0 || index >= size)
			return null;

		if (index == 0)
			return removeFirst();

		// 삭제하려면 바로 이전 노드를 찾아야 한다.
		Node<T> prev = getNode(index - 1);
		return removeAfter(prev);
	}

	// 입력된 데이터를 저장한 노드를 찾아 삭제한다.
	// 삭제된 노드에 저장된 스트링을 반환한다.
	public T remove(T item) {
		Node<T> p = head;
		Node<T> q = null;
		while (p != null && p.data.equals(item)) {
			q = p;
			p = p.next;
		}
		if (p == null)
			return null;
		// 바로 첫번재 노드가 맞는 경우
		if (q == null)
			return removeFirst();

		return removeAfter(q);
	}

	public T removeFirst() {
		if (head == null)
			return null;

		T oldData = head.data;
		head = head.next;
		size--;

		return oldData;
	}

	// 삭제할 노드의 바로 앞 노드의 주소가 필요하다. 삭제할 노드의 주소만으로는 삭제할 수 없다.
	public T removeAfter(Node<T> before) {
		if (before.next == null)
			return null;

		T oldData = before.next.data;
		before.next = before.next.next;
		size--;

		return oldData;
	}

	// index 에 저장된 데이터를 반환
	public T get(int index) {
		if (index < 0 || index >= size)
			return null;
		/*
		 * 아래와 코드가 거의 중복이 된다.. 좋은방법이 아니란 말이지 getNode 의 리턴값이 index 번째 주소값을 리턴하니까 리턴값의
		 * 데이터만 접근하면 우리가 찾는 값이다. 그러나 예외가 있다면 만약 주소값이 null 이 반환됐다면 null.data ? 이것은 말이
		 * 안돼(그냥 에러이기 때문에 .. 유효성체크를 해야한다)
		 * 
		 * Node<T> p = head;
		 * 
		 * for(int i=0; i<index; i++) p = p.next;
		 * 
		 * return p.data;
		 */
		return getNode(index).data;
	}

	// index 에 저장된 주소를 반환
	public Node<T> getNode(int index) {
		if (index < 0 || index >= size)
			return null;

		Node<T> p = head;

		for (int i = 0; i < index; i++)
			p = p.next;

		return p;

	}

	/*
	 * 연결리스트의 노드들을 처음부터 순서대로 방문하는 것을 순회 한다고 말한다. indexOf 메서드는 입력된 데이터 item과 동일한 데이터를
	 * 저장한 노드를 찾아서 그 노드번호(index)를 반환한다. 이 것을 위해 연결리스트를 순회한다.
	 */
	public int indexOf(T item) {
		// 첫번째 노드를 가리킨다
		Node<T> p = head;
		int index = 0;

		while (p != null) {
			// == 가 아닌 equals를 사용한다.
			if (p.data.equals(item))
				return index;

			p = p.next;
			index++;
		}

		return -1;
	}

	public static void main(String[] args) {
		MySingleLinkedList<String> list = new MySingleLinkedList<String>();

		list.add(0, "One");
		list.add(1, "Two");
		list.add(2, "Three");
		list.add(3, "four");

		System.out.println(list.get(2));
		System.out.println(list.remove(1));
		System.out.println(list.get(1));
	}

}

[ 실행결과 ]

Three
Two
Three