LinkedList

1. 리스트

  1) 리스트란?

    - 순서를 가지는 데이터의 집합

    - 값의 중복을 허용한다.

    - 순차 리스트와 연결 리스트로 나뉜다.

 

  2) 순차 리스트

    - 1차원 배열에 항목들을 순서대로 저장한다.

    - 데이터의 종류와 구조에 따라 구조화된 자료구조를 만들어 배열에 저장할 수도 있다.

    - 배열의 인덱스를 이용해 원하는 위치의 데이터에 접근할 수 있다.

    - 삽입 삭제 연산의 최악의 시간복잡도는 O(n)

    - 메모리 낭비, 새로운 배열 생성등의 문제가 있다.

 

  3) 연결 리스트

    - 개별적으로 위치하고 있는 각 원소를 연결하여 하느의 전체적인 자료구조를 이룬다.

    - 자료구조의 크기를 동적으로 조정 가능, 메모리의 효율적인 사용이 가능

    - 삽입, 삭제 연산에 유리, 조회 연산은 불리

 

---

 

2. 연결 리스트

  1) 기본 구조

    - 노드 : 데이터 필드, 링크 필드

    - 헤드 : 연결 리스트의 첫 노드에 대한 참고값을 갖고 있음

 

---

 

3. 단순 연결 리스트

  1) 연결 구조

    - 노드가 하나의 링크 필드에 의해 다음 노드와 연결되는 구조

    - 헤드가 가장 앞의 노드를 가리키고, 링크 필드가 연속적으로 다음 노드를 가리킨다.

    - 링크 필드가 Null인 노드가 연결 리스트의 마지막 노드이다.

 

  2) 코드

package com.algo.day6;

class LinkedList<E> {
	Node<E> first;
	int size;
	private static class Node<E> {
		private E item;
		private Node<E> next;
		Node (E item, Node<E> next) {
			this.item = item;
			this.next = next;
		}
		
		@Override
		public String toString() {
			return "Node [item=" + item + ", next=" + next + "]";
		}
	}

	LinkedList() {}
	
	public void add (int index, E item) { 
		Node<E> newNode = new Node<>(item, null);
		if (index == 0) {
			newNode.next = first;
			first = newNode;
		} else {
			Node<E> x = node(index - 1);
			newNode.next = x.next;
			x.next = newNode;
		}
		++size;
	}
	
	public void add(E item) {
		// 1. 새로운 노드를 생성
		Node<E> newNode = new Node<>(item, null);
		if (first == null) first = newNode;
		else {
			Node<E> last = node(size - 1);
			last.next = newNode;
		}
		++size;
	}
	
	private Node<E> node(int index) {
		Node<E> x = first;
		for (int i = 0; i < index; i++) {
			x = x.next;
		}
		return x;
	}
	
}