리스트(List)

리스트 정의

리스트는 데이터를 순서대로 나열한 자료구조이다. 선형 리스트 또는 연걸 리스트라고도 불린다.
연결 리스트의 종류는 단일 연결 리스트, 이중연결 리스트, 원행 연결 리스트 이렇게 세가지 기본 유형이 있다.

단일 연결 리스트^{singly-linked list}: 면접관분이 “연결 리스트”라고만 말한다면 보통 단일 연결 리스트를 뜻하는 것으로
보면 된다. 리스트에 들어가는 각 데이터 원소에는 리스트의 다음 원소에 대한 연결고리^link(포인터 또는 레퍼런스)가 들어 있다.
단일 연결 리스트의 첫 번째 원소는 리스트의 머리^head라고 부른다. 단일 연결 리스트의 마지막 원소는 꼬리^tail라고 부르며 연결고리는 비어 있거나 널 연결고리로 이어져 있다.
이중연결 리스트^{doubly-linked list}: 이중 연결리스트는 단일 연결 리스트의 여러 가지 단점을 극복하기 위해 만들어진 것이다.
이중연결 시트는 각 원소마다 리스트에서 그다음에 오는 원소에 대한 연결고리 외에 그 아펭 있는 원소에 대한 연결고리도 들어 있다는 점에서 단일 연결 리스트와 다르다.
원형 연결 리스트^{circularly-linked list}: 원형 리스트는 단일 연결 리스트로 된 것도 있고, 이중 연결 리스트로 된 것도 있다.
원형 연결 리스트에는 끝, 즉 머리나 꼬리가 없다. 원형 연결 리스트의 모든 원소에서 다음 원소를 가리키는 포인터나 레퍼런스에는 반드시 널 아닌 어떤 원소가 들어가며, 이중 연결 리스트라면 포인터/레퍼런스에도 널이 아닌 원소가 들어가야 한다. 원소가 하나밖에 없는 리스트라면 그냥 자기 자신을 가리키면 된다.

지금까지 단순 텍스트로만 설명을 해서 이해가 안되는 부분이 있을 수도 있다. 더 자세한 내용이나 부족한 내용을 학습하기 위해 연결 리스트 by 생활코딩에서 자세한 학습이 가능하다.

리스트 메서드

배열로 리스트를 구현한다. 구현하는 방법중 포인터, 커서 등이 있는데 포인터로 구현하는 리스트의 메서드를 설명토록 하겠다.

search(): 어떤 조건을 만족하는 노드를 검색하는 메서드.

public E search(E obj, Comparator<? super E> c) {
Node<E> ptr = head;							// 현재 스캔중인  노드

while (ptr != null) {
  if (c.compare(obj, ptr.data) == 0) {	// 검색 성공
    crnt = ptr;
    return ptr.data;
  }
  ptr = ptr.next;							// 다음 노드를 선택
}
return null;								// 검색 실패
}

addFirst(): 리시트의 머리에 노드를 삽입하는 메서드.

public void addFirst(E obj) {
Node<E> ptr = head;							// 삽입 전의 머리 노드
head = crnt = new Node<E>(obj, ptr);
}

addLast(): 리스트 꼬리에 노드를 삽입하는 메서드.

public void addLast(E obj) {
if (head == null)							// 리스트가 비어 있으면 
  addFirst(obj);							// 머리에 삽입
else {
  Node<E> ptr = head;
  while (ptr.next != null)
    ptr = ptr.next;
  ptr.next = crnt = new Node<E>(obj, null);
}
}

removeFirst(): 머리 노드를 삭제하는 메서드.

public void removeFirst() {
if (head != null)							// 리스트가 비어 있지 않으면
  head = crnt = head.next;
}

removeLast(): 꼬리 노드를 삭제하는 메서드.

public void removeLast() {
if (head != null) {
  if (head.next == null)					// 노드가 하나만 있으면
    removeFirst();						// 머리 노드를 삭제
  else {
    Node<E> ptr = head;					// 스캔 중인  노드
    Node<E> pre = head;					// 스캔 중인  노드의 앞쪽 노드

    while (ptr.next != null) {
      pre = ptr;
      ptr = ptr.next;
    }
    pre.next = null;					// pre는 삭제 후의 꼬리 노드
    crnt = pre;
  }
}
}

remove(): 임의의 노드를 삭제하는 메서드.

public void remove(Node p) {
if (head != null) {
  if (p == head)							// p가 머리 노드면
    removeFirst();						// 머리 노드를 삭제
  else {
    Node<E> ptr = head;

    while (ptr.next != p) {
      ptr = ptr.next;
      if (ptr == null) return;		// p가 리스트에 없습니다.  
    }
    ptr.next = p.next;
    crnt = ptr;
  }
}
}

removeCurrentNode(): 현재 선택한 노드를 삭제하는 메서드.
```
public void removeCurrentNode() {
  remove(crnt);
}
```

clear(): 모든 노드를 삭제하는 메서드.

public void clear() {
while (head != null)						// 노드에 아무것도 없을 때까지
  removeFirst();							// 머리 노드를 삭제
crnt = null;
}

next(): 선택 노드를 하나 뒤쪽으로 이동하는 메서드.

public boolean next() {
if (crnt == null || crnt.next == null)
  return false;							// 이동할 수 없음
crnt = crnt.next;
return true;
}

printCurrentNode(): 선택 노드를 표시하는 메서드.

public void printCurrentNode() {
if (crnt == null)
  System.out.println("선택한 노드가 없습니다.");
else
  System.out.println(crnt.data);
}

dump(): 리스트의 순서대로 모든 노드를 표시하는 메서드.

public void dump() {
Node<E> ptr = head;

while (ptr != null) {
  System.out.println(ptr.data);
  ptr = ptr.next;
}
}

리스트의 기능

리스트의 핵심적인 개념은 순서가 있는 엘리먼트의 모임이라는 것입니다.
빈 엘리먼트는 허용되지 않는다는 것도 기억해야 할 것입니다. 그리고 중복된 데이터를 허용한다는 것도 기억해두세요.
중복 허용은 배열과 리스트의 차이가 아닙니다. 배열도 중복이 허용됩니다.
중복 허용은 이후에 배울 set과 같은 데이터 스트럭쳐와의 차이라고 할 수 있습니다.
조금 이야기를 구체화합시다. 일반적으로 리스트 데이터 스트럭쳐는 아래와 같은 기능(operation)을 가지고 있습니다.

처음, 끝, 중간에 엘리먼트를 추가/삭제하는 기능
리스트에 데이터가 있는지를 체크하는 기능
리스트의 모든 데이터에 접근할 수 있는 기능
위와 같은 기능을 가지고 있고, 순서가 있으면서 중복이 허용된다면 그러한 데이터 스트럭쳐를 리스트라고 합니다.
참조: 생활코딩 - list

리스트 정의와 사용하는 메서드 그리고 기능을 알아보았다. 리스트 관련 코드 및 실제 사용예제의 경우 자료구조와 함께 배우는 알고리즘 입문 (자바 편) - List에서 확인할 수 있다.

참조

자료구조와 함께 배우는 알고리즘 입문 (자바 편)
생활 코딩

Date: July 2, 2020

Tags: Data Structure