01-3)연결 리스트<제네릭>

<쉽게 배우는 자료구조 with 자바>를 읽으며 학습한 내용을 정리하는 중 입니다.

연결 리스트는 앞선 내용을 살펴봤듯,  데이터 공간을 미리 설정할 필요없이 데이터의 양에 따른 가변적인 추가/삭제에 용이하다. 리스트에 원소가 얼마나 들어올지 예상하기는 쉽지 않으므로, 배열 리스트는 공간을 낭비하지 않는 것이 매우 어렵다. 

 

반면, 연결 리스트는 원소가 추가될 때마다 공간을 할당받아 추가하는 동적 할당 방식을 따르기에 배열의 공간 낭비를 피할 수 있는 자료구조로 자주 쓰인다. 

 

연결 리스트에 숨은 아이디어는 '노드'라고 불리는 요소이다. 노드는 원소를 저장하는 필드(item)와 다음 노드를 가리키는 필드(next)로 구성된다. item필드는 우리가 담을 값을 보유하는 객체이며, 필드 next는 다음 노드를 가리키는 링크(자바의 레퍼런스 c의 포인터)이다.

 

이해를 위해 추가적으로 들은 '생활 코딩'에서 제공해준 연결 리스트 이미지

 

 

연결 리스트에 접근하기 위해서는 첫 번째 노드부터 시작하는 특징을 지닌다. 배열 리스트처럼 물리적으로 연결되어 찾아가는 형태가 아닌 각 노드가 연결된 링크를 통해 접근하는 방식의 연결 리스트는 특징을 지닌다. 

따라서 연결리스트 객체는 리스트의 노드를 직접  저장할 필요가 없으며, 첫 번째 노드에 접글 할 수 있는 레퍼런스를 가지고 있으면 된다. ( 위의 HEAD에 해당한다. )

 

연결리스트를 구현하기에 앞서, 필요한 노드 클래스를 먼저 작성해보자.

package list;

public class Node<E> {
	public E item;
	public Node<E> next;

	public Node(E newitem) {
		item = newitem;
		next = null;
	}
	
	public Node(E newitem, Node <E> nextNode) {
		item = newitem;
		next = nextNode;	
	}
}

생성자로 파라미터가 2개인 경우와 1개인 경우로 나눠진다.

파라미터가 하나인 경우는 생성한 노드 객체가 가지는 값은 지정해주고, 다음 노드를 가르키는 링크는 알려주지 않는다.

파라미터가 두개인 경우는 생성한 노드 객체에 값을 지정해주고, 다음 노드를 가르키는 링크도 알려준다.

필요한 노드를 작성했다면, 이제 연결 리스트를 구현하기 위한 본격적인 코드를 살펴보자.

 

 

 

인터페이스의 경우, 앞선 배열 리스트를 구현함 필요했던 인터페이스와 같은 것을 사용한다.

package list;

public interface ListInterFace<E> {
	
	public void add(int i, E x);
	public void append(E x);
	public E remove(int i );
	public boolean removeItem(E x);
	public E get(int i);
	public void set(int i, E x);
	public int indexOf(E x);
	public int len();
	public boolean isEmpty();
	public void clear();
	
}

 

 

인터페이스를 토대로 연결리스트의 코드를 작성한 내용이다.

package list;

public class LinkedList<E> implements ListInterFace<E>{

	private Node<E> head;
	private int numitems;
	
	// 생성자
	public LinkedList() {
		numitems = 0;
		head = new Node<>(null, null);
	}
	
	
	// 리스트에 원소 x 삽입하기
	public void add(int index, E item) {
		if(index >=0 && index <= numitems) {
			Node<E> prevNode = getNode(index-1);
			Node<E> newNode = new Node<>(item, prevNode.next);
			prevNode.next = newNode;
			numitems++;
		}
	}
	
	// 리스트 뒤에 추가
	public void append(E item) {
		Node<E> prevNode = head;
		while (prevNode.next != null) {
			prevNode = prevNode.next;
		}
		
		Node<E> newNode = new Node<>(item, null);
		prevNode.next = newNode;
		numitems++;
	}
	
	// 원하는 인덱스의 값을 제거
	public E remove(int index) {
		if(index >= 0 && index < numitems) {
			Node<E> prevNode = getNode(index -1);
			Node<E> currNode = prevNode.next;
			prevNode.next = currNode.next;
			numitems--;
			return currNode.item;
		} else 
			return null;
	}
	
	// 원하는 원소제거
	public boolean removeItem(E x) {
		Node<E> currNode = head; //더미헤드
		Node<E> prevNode; 
		for(int i =0; i< numitems; i++) {
			prevNode = currNode;
			currNode = currNode.next;
			if(((Comparable)(currNode.item)).compareTo(x)==0) {
				prevNode.next = currNode.next;
				numitems--;
				return true;
			}
		}
		return false; // 제거 대상이 없다면
	}
	
	// 원하는 인덱스의 원소 알기
	public E get(int index) {
		if(index >= 0 && index <= numitems - 1) {
			return getNode(index).item;
		} else {
			return null;
		}
	}
	
	
	
	public Node<E> getNode(int index) {
		if(index >= -1 && index <= numitems-1) {
			Node<E> currNode = head;	// 더미 노드
			for(int i =0; i<= index; i++) {
				currNode = currNode.next;
			}
			return currNode;
		} else {
			return null;
		}
	}
	
	//연결 리스트의 K번째 원소를 x로 대체하기
	public void set (int index, E x) {
		if(index >= 0 && index <= numitems-1) {
			getNode(index).item = x;
		} else {
			/*예외처리*/
		}
	}
	
	// 원소 x가 연결 리스트의 몇 번째 원소인지 알기
	public final int NOT_FOUND = -12345;
	public int indexOf(E x) {
		Node<E> currNode =head; // 더미 노드
		int i;
		for(i =0; i < numitems; i++) {
			currNode = currNode.next;
			if(((Comparable)(currNode.item)).compareTo(x)==0) {
				return i;
			}
		}
		return NOT_FOUND;
	}
	
	
	// 리스트의 총 원소 수 알려주기
	public int len() {
		return numitems;
	} 
	
	
	// 리스트가 비었는지 알려주기
	public boolean isEmpty() {
		return numitems == 0;
	}
	
	
	// 리스트 청소하기
	public void clear() {
		numitems =0;
		head = new Node<>(null, null);
	}
}