[자료구조] Array List, Linked List

1. List 

순서가 있는 데이터의 집합, 데이터 중복 허용한다. 배열과는 다르게 크기 지정에 한계가 없으므로 크기를 지정할 필요가 없다.

2. Array List 

배열로 이루어진 리스트이다. 기존의 Vector class를 개선한 것이다. 논리적인 저장순서와 물리적인 저장순서가 동일하다. 데이터 삽입시 만약 첫번째 자리에 새로운 데이터를 추가할 경우(worst case) 모든 원소들을 1씩 shift 해야 한다. 이 경우 시간복잡도는 O(n)에 해당한다. 

3. Linked List

연결리스트: 자료들을 임의의 기억공간에 기억하며. 일렬로 연결된 자료를 저장할때 사용한다. 
자료 항목의 순서에 따라 노드의 포인터 부분을 이용하여 서로 연결시킨 자료구조이다. (= 논리적 저장 순서와 물리적 저장 순서가 일치하지 않는다.) 연결을 위한 링크(포인터) 부분이 필요하기 때문에 순차 리스트에 비해 기억공간 이용효율이 좋지 않다. 
노드의 삽입, 삭제 작업이 용이하다. 기억공간이 연속적으로 놓여있지 않아도 저장이 가능하다.

하지만, 검색 과정에서는 첫 번째 노드부터 순차적으로 모두 확인해야 하므로 O(n)의 시간복잡도를 가진다.
접근 속도가 느리다. 연결리스트 중에서 중간 노드의 연결이 끊어지면 그 다음 노드를 찾기 힘들다.
Tree구조의 근간이 되는 자료구조, Tree에서 사용되었을 때 그 유용성이 드러난다. 
희소행렬을 연결리스트로 표현하면 기억장소가 절약된다.
- Sparse Matrix  : 행렬의 요소 중 많은 항들이 0 으로 되어있는 매트릭스. 

단/양방향 Linked List

- 단방향 : 한 방향으로만 데이터가 이동할 수 있다. 헤더 주소 하나만 포인터를 저장하고 있다.
- 양방향 : 앞뒤로 연결된 노드의 주소를 가지고있어 양방향으로 이동이 가능. 양 쪽끝에 포인터를 저장하고 있어서 맨 끝에 노드를 삽입할때 간단하다.

단/양방향 Linked List 구현

package com;

public class SingleLinkedList {
	public static void main(String[] args){
		LinkedList ll = new LinkedList();
		ll.append(1);
		ll.append(2);
		ll.append(3);
		ll.append(4);
		ll.retieve();
		ll.delete(2);
		ll.retieve();
	}
}

//단방향 LinkedList 만들기
class LinkedList{
	Node header;
	static class Node{
		int data;
		Node next = null;
	}
	LinkedList(){
		header = new Node();
	}

	//데이터 추가
	void append(int d){
		Node end = new Node();
		end.data = d; //포인터
		Node n = header;
		while(n.next!=null){ //마지막 노드가 아닐때까지 반복
			n=n.next;
		}
		n.next = end; //마지막 노드로 데이터 추가
	}
	//데이터 삭제
	void delete(int d){
		Node n = header; //포인터
		while(n.next != null){ //마지막 노드가 아닐때까지 반복
			if(n.next.data == d){
				n.next = n.next.next; //포인터를 다다음 노드로 변경, 연결을 바꿔버림
			}else{
				n = n.next;
			}
		}
	}
	//전체 노드를 출력
	void retieve(){
		Node n = header.next;//헤더의 다음번 데이터부터 출력
		while(n.next!=null){
			System.out.print(n.data + " -> ");
			n = n.next;
		}
		System.out.println(n.data);
	}
}

실행결과

4. Array List 와 Linked List의 비교

순차적인 삭제, 삽입, 검색시에는 Array List 가 좋다.
비순차적인 데이터들을 삭제, 삽입시에는 Linked List 가 좋다.

참조 유투브 영상 : https://www.youtube.com/watch?v=DzGnME1jIwY&list=PLjSkJdbr_gFZQp0KEoo0Y4KkCI5YqxtjZ