[자료구조] List 개념 정리

자료구조

List는 자료구조의 일종으로, 자료구조란 자료의 집합을 의미하며, 더 나아가 저장, 삭제, 조회 등을 할 수 있도록 표현한 것이다.

자료구조는 선형 자료구조와 비선형 자료구조로 나뉘게 되는데, 그중 List는 선형 자료구조이다.

전체 자료구조 리스트는 다음과 같다.

 

자료구조 구성도

 

 

 

List

List는 대표적인 자료구조 중 하나이며, 이후 학습할 내용인 Tree, Graph 등 다른 자료구조에 비해  통상적으로 난이도가 쉽다고 할 수 있다.

배열과 비슷한 구조를 띄고 있지만, 배열의 치명적인 단점인 크기가 고정적이라는 점을 해결할 수 있는 방법이다.

 

시간 복잡도

- 조회

  O(n)

- 삽입, 삭제(가장 앞, 뒤)

  O(1)

 

시간 복잡도에서 나타내는 것과 같이, 조회는 느리지만, 단순히 맨 앞 또는 뒤에 값을 추가하고 삭제하면 되므로 삽입과 삭제가 가장 빠른 자료구조이다.

따라서 조회보다는 삽입과 삭제가 빈번한 데이터를 관리할 경우 사용되면 좋은 자료구조이다.

 

메커니즘

배열과 리스트는 메커니즘이 비슷하다.

배열의 가장 큰 특징인 데이터가 나란히 저장된다는 특징을 리스트도 고스란히 갖고 있으며, 그 형태도 비슷한 형태로 다음과 같다.

참고로 리스트의 종류는 단방향, 양방향, 원형 리스트가 존재하며, 다음의 그림은 양방향 리스트가 기준이다.

배열과 리스트 저장 방식

배열보다 연결성에 좀 더 중점을 두어 구현된 자료구조로, 저장 단위를 흔히 노드(Node)라고 표현하며, 각각의 노드들은 이전/다음 노드의 정보를 가지고(연결되고) 있다.

 

조회

리스트는 기존 배열만 알고 있던 사람들의 입장에서는 조금 특이한 저장 방식을 갖는다.

1. 가장 앞 단의 노드 참조 및 값 비교

2. 연결된 바로 다음 노드 참조 및 값 비교

3. 값을 찾을 때까지 반복

이렇게 하나하나씩 앞으로 나아가며 값을 찾는 방식이며, 말 그대로 하나하나 비교를 하기 때문에 찾으려는 데이터가 가장 뒤에 있거나 없는 경우의 시간 복잡도가 O(n)이 나오게 되는 것이다.

 

저장

저장은 굉장히 단순하다. 앞 또는 뒤에 데이터를 추가해 주는 작업만 하면 된다.

1. 가장 앞/뒤 노트 조회

2. 값 저장

 

삭제

삭제도 저장과 동일하다.

1. 가장 앞/뒤 노드 조회

2. 값 삭제

 

노드 연결 상태 재정비

바로 앞에서 저장과 삭제가 굉장히 쉬운 것처럼 말했지만, 이건 한 가지를 빼놓고 말했기 때문이다.

그건 바로 연결 상태 관리에 대한 것이며, 리스트는 이 연결 상태에 대한 관리를 늘 해주어야 한다.

 

예를 들어, 다음과 같이 데이터가 저장되어 있다고 생각해 보자.

이 상태에서 중간에 있는 노드를 삭제한다면, 다음과 같이 될 것이다.

 

해당 그림이 의미하는 내용은 다음/이전 노드를 가리키는 연결 상태가 망가졌다는 점이다.

이를 다시 보강하고, 최종적으로 다음과 같은 형태를 나타내게 해야 한다.

 

구현

package List.LinkedList;

// 양방향 연결 리스트
public class LinkedList {
	// 노드 정의
	private class Node {
		Node prev; // 이전 노드의 정보를 가지고 있는 객체
		int data; // 현재 노드에 들어있는 값
		Node next; // 다음 노드의 정보를 가지고 있는 객체

		Node() {}
		
		// 노드에 값을 바로 삽입하기 위한 생성자
		Node(int data) {
			this.data = data;
		}
	}

	private Node head; // 가장 앞 노드의 정보를 가지고 있음
	private Node tail; // 가장 뒤 노드의 정보를 가지고 있음
	private Node cur; // 현재 가리키고 있는 노드의 정보를 가지고 있음
	private int size; // 현재 리스트의 크기

	// 노드 초기화를 위한 생성자 정의
	public LinkedList() {
		head = new Node();
		tail = new Node();
		cur = new Node();

		size = 0;
	}

	public void add(int data) {
		// 첫 데이터 추가인 경우와 아닌 경우 구분
		if (size == 0) {
			Node newNode = new Node(data);

			head.next = newNode;
			newNode.prev = head;

			newNode.next = tail;
			tail.prev = newNode;

			size++;
		} else {
			Node newNode = new Node(data);

			// 마지막 노드로 이동.
			cur = head.next;
			while (cur.next != tail) {
				cur = cur.next;
			}

			cur.next = newNode;
			newNode.prev = cur;

			newNode.next = tail;
			tail.prev = newNode;

			size++;
		}
	}

	public void add(int data, int index) {
		// 전체 크기보다 큰 곳에 데이터를 삽입하려는 경우
		if(index > size) {
			System.out.println("Please try again");
			return;
		}
		
		// 첫 데이터 추가인 경우와 아닌 경우 구분
		if (size == 0) {
			Node newNode = new Node(data);

			head.next = newNode;
			newNode.prev = head;

			newNode.next = tail;
			tail.prev = newNode;

			size++;
		} else {
			Node newNode = new Node(data);

			// 마지막 노드로 이동
			cur = head.next;
			for(int i = 0; i < index; i++) {
				cur = cur.next;
			}

			cur.next = newNode;
			newNode.prev = cur;

			newNode.next = tail;
			tail.prev = newNode;

			size++;
		}
	}

	public int remove(int index) {
		Node rNode;
		
		// 데이터 초과일 경우
		if(index > size) {
			System.out.println("Please try again");
			return -1;
		}
		
		// 인덱스 값 찾아가기
		cur = head.next;
		for(int i = 0; i < index; i++) {
			cur = cur.next;
		}
		rNode = cur;
		 
		// 이전 노드와 이후 노드 포인터 변경
		cur.prev.next = cur.next;
		cur.next.prev = cur.prev;
		size--;
		
		return rNode.data;
	}

	public int size() {
		return size;
	}

	public int indexOf(int data) {
		int count = 0;
		boolean bFind = false;
		
		cur = head.next;
		while(cur.next != tail) {
			if(cur.data == data) {
				bFind = true;
				break;
			}
			cur = cur.next;
			count++;
		}
		
		if(bFind) {
			return count;
		}else {
			return -1;
		}
	}

	public String toString() {
		String str = "";
		cur = head.next;
		str = String.valueOf(cur.data);
		
		while(cur.next != tail) {
			cur = cur.next;
			str += String.valueOf(", " + cur.data);
		}
		
		return str;
	}

}

Github : https://github.com/WOOOOOOOONG/Learning-Algorithm

WOOOOOOOONG/Learning-Algorithm

틀린 내용 또는 질문 있으시면, 편하게 댓글 남겨주시면 감사하겠습니다.