LinkedList

배열 리스트의 단점

배열 리스트는 내부에 배열을 사용해서 데이터를 보관하고 관리한다.

• 배열은 필요한 배열의 크기를 미리 확보해야한다. 따라서 사용하지 않는 나머지 공간은 사용되지 않고 낭비된다.
• 데이터를 추가할 때 데이터의 공간을 확보해야 하기 때문에 기존 데이터들을 이동시켜야 하는데, 많은 데이터를 이동시켜야 하기 때문에 성능 면에서 좋지 않다.

Node

public class Node{
	Object item;
	Node next;
}

노드 클래스는 내부에 저장할 데이터 item과 다음 노드의 참조값 next를 가진다.

Node 연결하기

//노드 생성 후 연결
Node first = new Node("nodeA");
first.next = new Node("nodeB");

노드의 연결상태를 확인하기 위한 toString()

@Override
public String toString(){
	StringBuilder sb = new StringBuilder();
    Node x = this;
    sb.append("[");
    while (x != null){
		sb.append(x.item);
		if(x.next != null) {
             sb.append("->");
        }
        x = x.next;
   	}
    sb.append("]");
	return sb.toString();
} 

LinkedList의 메소드

• 모든 노드 탐색(printAll)
• 마지막 노드 조회(getLastNode)
• 특정 index의 노드 조회(getNode)
• 노드에 데이터 추가(add)

1. 모든 노드 탐색

private static void printAll(Node node){
	Node x = node;
	while (x != null){
		System.out.println(x.item);
        x = x.next;
    }
}

2. 마지막 노드 조회

private static Node getLastNode(Node node){
	Node x = node;
	while (x.next != null){
		x = x.next;
	}
	return x;
}

3. 특정 위치 노드 조회

private static Node getNode(Node node, int index){
	Node x = node;
	for(int i=0; i< index; i++){
		x = x.next;
	}
    return x;
} 

4. 노드에 데이터 추가

private static void add(Node node, String param){
	Node lastNode = getLastNode(node);
	lastNode.next = new Node(param);
}

특정 위치에 있는 데이터를 추가/삭제하는 기능

그림으로 이해해보기

기존에 참조하고 있던 연결을 바꿔주면 된다.

위 그림과 코드를 같이 보면서 이해하면 쉽다.

삭제 코드

배열 리스트와 연결 리스트 비교

• 배열리스트
  1. 인덱스로 마지막 위치를 바로 찾을 수 있다.
  2. 데이터를 마지막에 추가하면 데이터를 이동하지 않아도 된다.
• 연결 리스트
  1. 노드를 마지막까지 순회해야 마지막노드를 찾는다.
  2. 데이터를 추가하는 경우 일부 노드의 참조만 변경하면 된다.

Generic 도입

연결리스트의 타입 안전성을 높이고 싶다면 Genenric을 도입하면 된다.
기존에 Object 타입을 바꿔주면 된다.

List 자료구조

리스트: 자바의 컬렉션 프레임워크가 제공하는 대표적인 자료구조

Collection<Interface>

: List, Set, Queue와 같은 다양한 하위 인터페이스가 있다.
List 인터페이스에는 ArrayList, LinkedList와 같은 클래스가 있다.

1. ArrayList
   (1) 배열을 사용해서 데이터를 관리
   (2) 기본 CAPACITY = 10이고 넘어갈때마다 50%증가
   (3) 메모리 고속복사 연산 사용
   : ArrayList의 중간 위치에 데이터를 추가하면, 추가할 위치 이후의 모든 요소를 한칸씩 뒤로 이동시켜야하는데, 자바는 이 부분을 최적화한다. 메모리 고속복사 연산을 사용해 연산을 빠르게 수행한다.(cf System.arraycopy() 사용)
2. LinkedList
   (1) 이중 연결 리스트 구조
   (2) 첫 번째 노드와 마지막 노드 둘다 참조

이중 연결리스트

class Node {
	E item;
   Node next;
   Node prev;
}
class LinkedList{
	Node first; //첫 번째 노드 참조
   Node last;	//마지막 노드 참조
   int size;
}