3:56

1. LinkedList란?

연결 리스트(LinkedList)란 각 노드가 데이터(item)와 포인터(next)를 가지고 한 줄로 연결되어 있는 방식으로 데이터를 저장하는 자료 구조이다. 연결리스트의 대표적 종류에는 단일 연결 리스트, 양방향 연결 리스트, 원형 연결 리스트가 있다.

• 선언시 크기가 고정되어 있지 않다.
• 데이터 접근시 처음부터 노드를 순회해야 하므로 배열 리스트에 비해 속도가 느리다.
• 데이터 추가/삭제시 전후 노드의 포인터만 수정하면 되므로 배열 리스트에 비해 속도가 빠르다.

2. LinkedList 구현하기

구현할 내용은 아래와 같다.

• add (int i, E x) - i번째 인덱스에 원소 x를 입력한다.
• append (E x) - 배열 리스트의 끝에 원소 x를 입력한다.
• remove (int i) - i번째 원소를 삭제한다.
• removeItem (E x) - 배열 리스트에서 원소 x를 삭제한다. 중복 원소가 있을 경우 먼저 나오는 원소를 삭제한다.
• get (int i) - i번째 원소를 리턴한다.
• set (int i, E x) - i번째 인덱스의 원소를 x로 교체한다.
• len() - 배열 리스트의 원소 개수를 리턴한다.
• isEmpty() - 배열 리스트가 비었는지 여부를 boolean으로 리턴한다.
• clear() - 인덱스를 비운다.
• indexOf(E x) - 배열 리스트 원소 x의 인덱스를 리턴한다. 중복 원소가 있을 경우 먼저 나오는 원소 인덱스를 리턴한다.
• printAll() - 배열 리스트의 모든 원소를 리턴한다.

1) 노드 클래스

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;
	}
}

• item 변수에 데이터를 저장한다.
• next 변수에 다음 노드를 저장한다. next는 다음 노드의 위치를 가리키는 포인터가 된다.
• 첫 번째 생성자는 데이터를 입력받아 데이터를 item에 저장하고, 포인터 값은 null로 저장한다.
• 두 번째 생성자는 데이터와 다음 노드를 입력받아 데이터를 item에 저장하고, 포인터 값에 다음 노드를 저장한다.

2) 인터페이스

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

3) LinkedList 클래스

- 필드 영역

//필드 영역
	private Node<E> head;
	private int size;

• head 변수에는 연결 리스트의 시작 노드를 저장한다.
• size에는 연결 리스트의 길이를 저장한다.

- 생성자 영역

	//생성자 영역
	public LinkedList() {
		size=0;
		head = new Node<>(null,null);
	}

• 새 연결 리스트를 생성하면 필드 영역의 head에 데이터와 포인터값이 모두 null인 새 노드를 저장한다.
• 연결 리스트의 크기인 size는 0이다.

- 메서드 영역

<getNode 메서드 구현>

public Node<E> getNode (int i) {
		if (i<-1||i>size) throw new IllegalArgumentException();
		Node<E> currNode = head;
		for (int j=0; j<=i; j++) {
			currNode=currNode.next;
		}
		return currNode;
	}

• 예외처리 - 입력받은 인덱스가 범위를 벗어나는 경우 (-1인 경우 더미 헤드를 반환)
• 인터페이스의 메서드를 오버라이딩 한 것은 아니다.
• head 노드를 currNode 변수에 저장한다.
• 입력받은 인덱스에 도달할 때까지 head부터 i만큼 포인터를 통해 다음 노드로 이동한 뒤 currNode를 리턴한다.

<add 메서드 구현>

	@Override
	public void add(int i, E x) {
		if (i<0||i>size) throw new IllegalArgumentException();
		Node<E> prevNode = getNode(i-1);
		Node<E> newNode = new Node<> (x,prevNode.next);
		prevNode.next=newNode;
		size++;
	}

• 예외처리 - 입력받은 인덱스가 범위를 벗어나는 경우
• x를 item으로 하고 prevNode.next를 next로하는 newNode를 생성한다.
• prevNode가 next로 newNode를 참조하게 한다.
• size 변수를 1 증가시킨다.

<append 메서드 구현>

	@Override
	public void append(E x) {
		Node<E> prevNode = getNode(size-1); 
		Node<E> newNode = new Node<>(x,null);
		prevNode.next=newNode;
		size++;

• prevNode에 연결 리스트의 마지막 인덱스 노드를 저장한다.
• item에 입력 받은 데이터를, next에 null값을 입력한 newNode 객체를 생성한다.
• prevNode가 next로 newNode를 참조하게 한다.

<remove 메서드 구현>

	@Override
	public void remove(int i) {
		if (i<0||i>size-1) throw new IllegalArgumentException();
		Node<E> prevNode = getNode(i-1);
		prevNode.next=getNode(i+1);
		size--;
	}

• 예외처리 - 입력받은 인덱스가 범위를 벗어나는 경우
• prevNode가 next로 prevNode.next를 생략하고 prevNode.next.next를 참조하게 한다.

<removeItem 메서드 구현>

	@Override
	public void removeItem(E x) {
		Node<E> currNode = head;
		Node<E> prevNode;
		
		for (int i=0; i<size; i++) {
			prevNode=currNode;
			currNode=prevNode.next;
			
			if (currNode.item.equals(x)) {
				prevNode.next=currNode.next;
				size--;
				return;
			}
		}
		
	}

• for문으로 연결 리스트를 순회한다.
• currNode의 데이터가 x와 일치하면 prevNode가 next값으로 currNode를 생략하고 currNode.next를 참조하게 한다.

<get,set,len,isEmpty 메서드 구현>

	@Override
	public E get(int i) {
		if (i<0||i>size-1) throw new IllegalArgumentException();
		Node<E> currNode = getNode(i);
		return currNode.item;
	}

	@Override
	public void set(int i, E x) {
		if (i<0||i>size-1) throw new IllegalArgumentException();
		Node<E> currNode = getNode(i);
		currNode.item=x;
	}

	@Override
	public int len() {
		return size;
	}

	@Override
	public boolean isEmpty() {
		return (size==0);
	}

• get - 입력받은 인덱스에 해당하는 값을 리턴한다.
• 예외처리 - 입력받은 인덱스가 범위를 벗어나는 경우
• set - 입력받은 인덱스에 해당하는 값을 입력받은 값으로 교체한다.
• 예외처리 - 입력받은 인덱스가 범위를 벗어나는 경우
• len - size 변수를 리턴한다.
• isEmpty - size==0 여부를 리턴한다.

<clear 메서드 구현>

	@Override
	public void clear() {
		size = 0;
		head = new Node<>(null,null);
	}

• size 변수를 0으로 초기화한다.
• head 변수를 새로운 노드로 초기화한다.

<indexOf 메서드 구현>

	@Override
	public int IndexOf(E x) {
		
		int idx=-1;
		Node<E> currNode = head;
		
		for (int i=0; i<size; i++) {
			currNode=currNode.next;
			
			if (currNode.item.equals(x)) {
				idx=i;
				break;
			}
		}
		
		return idx;
	}

• for문으로 연결 리스트를 순회하며 노드를 변수 currNode에 저장한다.
• currNode.item과 입력받은 x를 비교한다.
• currNode.item==x일때의 인덱스를 리턴한다.
• 만약 x와 같은 값이 없으면 -1를 리턴한다.

<printAll 메서드 구현>

	@Override
	public void printAll() {
		
		Node<E> currNode = head;
		
		for (int i=0; i<size; i++) {
			currNode=currNode.next;
			System.out.print(currNode.item+" ");
		}
		
		System.out.println();
		
	}

• for문으로 연결 리스트를 순회하며 노드를 변수 currNode에 저장한다.
• 매 순회마다 currNode.item을 출력한다.

- 전체 코드

public class LinkedList<E> implements ListInterface<E> {
	
	//필드 영역
	private Node<E> head;
	private int size;
	
	//생성자 영역
	public LinkedList() {
		size=0;
		head = new Node<>(null,null);
	}
	
	//메서드 영역
	
	public Node<E> getNode (int i) {
		if (i<-1||i>size) throw new IllegalArgumentException();
		Node<E> currNode = head;
		for (int j=0; j<=i; j++) {
			currNode=currNode.next;
		}
		return currNode;
	}
	
	@Override
	public void add(int i, E x) {
		if (i<0||i>size) throw new IllegalArgumentException();
		Node<E> prevNode = getNode(i-1);
		Node<E> newNode = new Node<> (x,prevNode.next);
		prevNode.next=newNode;
		size++;
	}

	@Override
	public void append(E x) {
		Node<E> prevNode = getNode(size-1); //while문으로 prevNode.next==null일때까지 순회해서 찾는 것도 가능
		Node<E> newNode = new Node<>(x,null);
		prevNode.next=newNode;
		size++;
		
	}

	@Override
	public void remove(int i) {
		if (i<0||i>size-1) throw new IllegalArgumentException();
		Node<E> prevNode = getNode(i-1);
		prevNode.next=getNode(i+1);
		size--;
	}

	@Override
	public void removeItem(E x) {
		Node<E> currNode = head;
		Node<E> prevNode;
		
		for (int i=0; i<size; i++) {
			prevNode=currNode;
			currNode=prevNode.next;
			
			if (currNode.item.equals(x)) {
				prevNode.next=currNode.next;
				size--;
				return;
			}
		}
		
	}

	@Override
	public E get(int i) {
		if (i<0||i>size-1) throw new IllegalArgumentException();
		Node<E> currNode = getNode(i);
		return currNode.item;
	}

	@Override
	public void set(int i, E x) {
		if (i<0||i>size-1) throw new IllegalArgumentException();
		Node<E> currNode = getNode(i);
		currNode.item=x;
	}

	@Override
	public int len() {
		return size;
	}

	@Override
	public boolean isEmpty() {
		return (size==0);
	}

	@Override
	public void clear() {
		
		size = 0;
		head = new Node<>(null,null);
		
	}

	@Override
	public int IndexOf(E x) {
		
		int idx=-1;
		Node<E> currNode = head;
		
		for (int i=0; i<size; i++) {
			currNode=currNode.next;
			
			if (currNode.item.equals(x)) {
				idx=i;
				break;
			}
		}
		
		return idx;
	}

	@Override
	public void printAll() {
		
		Node<E> currNode = head;
		
		for (int i=0; i<size; i++) {
			currNode=currNode.next;
			System.out.print(currNode.item+" ");
		}
		
		System.out.println();
		
	}

}

3) 결과 확인하기

<코드>

public class Test {
	public static void main(String[] args) {

	LinkedList<Integer> lst = new LinkedList<>();
	
	lst.add(0, 100);
	
	lst.add(1, 200);
	
	lst.add(2, 300);
	
	lst.append(400);
	
	lst.printAll();
	
	//100,200,300,400을 차례로 입력하고 출력합니다.
	
	lst.remove(0);
	
	lst.printAll();
	
	lst.removeItem(400);
	
	lst.printAll();
	
	//0번째 인덱스의 값과 내용물이 400인 값을 삭제하고 출력합니다.
	
	lst.IndexOf(300);
	
	//300의 인덱스를 출력합니다.
	
	System.out.println(lst.isEmpty());
	System.out.println(lst.len());
	
	//lst가 비었는지 여부와 lst의 길이를 출력합니다.
	
	System.out.println(lst.get(0));
	
	//인덱스 0의 값을 출력합니다.
	
	lst.set(0, 1000);
	
	lst.printAll();
	
	//인덱스 0의 값을 1000으로 바꾸고 출력합니다.
	
	}
}

<결과>

정상적으로 출력된다.