[JAVA] 자료구조 클래스 - LinkedList(연결리스트)

1. LinkedList(연결리스트)

• LinkedList란 각 노드가 데이터와 포인터를 가지고 한 줄로 연결되어 있는 방식으로 데이터를 저장하는 자료구조이다.
• 이름에서 말하듯이 데이터를 담고 있는 노드들이 연결되어 있는데, 노드의 포인터가 다음이나 이전의 노드와의 연결을 담당한다.
• 늘어선 노드의 중간지점에서도 자료의 추가와 삭제가 O(1)의 시간에 가능하다는 장점을 갖는다. 그러나 배열이나 트리 구조와는 다르게 특정 위치의 데이터를 검색해 내는데에는 O(n)의 시간이 걸린다는 단점이 있다.

2. LinkedList(연결리스트)의 구조

• 노드(Node)와 링크(Link)로 구성된다.
• 노드(Node) : 실제 정보를 담고 있는 하나의 단위이다.
• 링크(Link) : 노드간의 위치정보를 저장하고 있어 연결리스트의 순서를 유지할 수 있도록 하는 연결고리다.
• 노드의 시작점은 head. 끝점은 tail이라 부르며 노드의 추가, 삭제, 탐색이 가능하다.

3. LinkedList(연결리스트)의 종류

가. 단일 연결리스트(Singly LinkedList)

• 각 노드에 자료 공간과 한 개의 포인터 공간이 있고, 각 노드의 포인터는 다음 노드를 가리킨다.

나. 이중 연결리스트(Doubly LinkedList)

• 구조는 단일 연결리스트와 비슷하지만, 포인터 공간이 두 대가 있고 각각의 포인터는 앞의 노드와 뒤의 노드를 가리킨다.

다. 원형(환형) 연결리스트(Circular LinkedList)

• 일반적인 연결리스트에 마지막 노드와 처음 노드를 연결시켜 원형으로 만든 구조이다.

라. 이중 원형(환형) 연결리스트(Doubly Circular LinkedList)  

• 이중 연결리스트의 마지막 노드와 처음 노드를 연결시켜 원형으로 만든 구조이다.

4. 배열과의 비교

가. 배열

• 배열은 각 값마다 고유한 인덱스를 가지고 있다. 이는 탐색에는 매우 유리하지만 삽입이나 삭제를 하는 부분에서 단점이 있다.
• 예를 들어 [1, 2, 3, 4, 5, 6]이라는 배열에서 3과 5사이에 4를 삽입하고 싶다면 5, 6의 인덱스를 뒤로 한칸씩 밀고 4를 를 빈 자리에 넣어줘야 한다. 이와 같은 과정은 배열의 복사, 이동을 통해 생기며, 삽입, 삭제의 규모가 커진다면 이는 많은 소요를 필요로 한다.

나. LinkedList

• LinkedList는 위와 같은 배열의 단점을 해결하기 위해 나왔다.
• LinkedList에서의 삽입은 삽입할 노드의 위치의 이전노드, 다음노드와 연결만 해주면 되고, 삭제도 마찬가지로 삭제하고 싶은 노드에 연결되어 있는 앞 뒤의 노드를 서로 이어주면 된다.
• 하지만 LinkedList는 탐색을 위해서는 항상 첫번째 노드부터 비교해야 한다는 담점이 있다.
• 위에서 설명한 내용과 같이, 배열과 LinkedList는 장단점이 반대이므로 데이터 탐색이 많이 필요한 상황에서는 배열을 사용하고 데이터 삽입, 삭제가 많이 필요한 상황에서는 LinkedList를 사용하는 것이 효율적이다.

5. LinkedList의 함수들

• public E getFirst() : 리스트의 첫 번째 값 리턴
  
• public E getLast() : 리스트의 마지막 번째 값 리턴
  
• public E removeFirst() : 리스트의 첫 번째 값 삭제
  
• public E removeLast() : 리스트의 마지막 값 삭제
  
• public void addFirst(E e) : 리스트의 첫 번째에 특정 요소 삽입
  
• public void addLast(E e) : 리스트의 마지막번째에 특정 요소 삽입
  
• public boolean contains(Object o) : 특정 요소가 있으면 true, 없으면 false 리턴
  
• public int size() : 리스트의 요소의 갯수를 리턴
  
• public boolean add(E e) : 리스트의 마지막번째에 특정 요소 추가 -> addLast()와 동일
  
• public boolean remove(Object o) : 특정 요소가 존재하면, 삭제
  
• public boolean addAll(Collection<? extends E> c) : 리스트의 마지막번째에 모든 Collection 요소 추가
  
• public boolean addAll(int index, Collection<? extends E> c) : 리스트의 특정 번째부터 모든 Collection 요소 추가
  
• public void clear() : 리스트의 모든 요소 삭제
  
• public E get(int index) : 리스트의 특정 번째의 요소 리턴
  
• public E set(int index, E element) : 리스트의 특정 번째에 특정 요소 추가
  
• public void add(int index, E element) : 리스트의 특정 번째에 특정 요소 추가
  
• public E remove(int index) : 리스트의 특정 요소 삭제, 삭제된 요소 리턴
  
• public int indexOf(Object o) : 리스트에서 처음으로 검출된 요소 리턴, 요소가 없으면 가장 낮은 인덱스 리턴
  
• public int lastIndexOf(Object o) : 리스트에서 마지막으로 검출된 요소 리턴, 요소가 없으면 가장 높은 인덱스 리턴
  
• public E peek() : 리스트의 첫 요소 가져옴 (삭제는 하지 않음)
  
• public E element() : 리스트의 첫 요소 가져옴 (삭제는 하지 않음)
  
• public E poll() : 리스트의 첫 요소 가져오고 삭제
  
• public E remove() : 리스트의 첫 요소 가져오고 삭제
  
• public boolean offer(E e) : 리스트의 마지막번째에 특정 요소 추가
  
• public boolean offerFirst(E e) : 리스트의 맨 앞에 특정 요소 추가
  
• public boolean offerLast(E e) : 리스트의 맨 뒤에 특정 요소 추가
  
• public E peekFirst() : 리스트의 첫 요소 가져옴 (삭제는 하지 않음), 리스트가 비어있으면 null 리턴
  
• public E peekLast() : 리스트의 마지막 요소 가져옴 (삭제는 하지 않음), 리스트가 비어있으면 null 리턴
  
• public E pollFirst() : 리스트의 첫 요소 가져와서 삭제, 리스트가 비어있으면 null 리턴
  
• public E pollLast() : 리스트의 마지막 요소 가져와서 삭제, 리스트가 비어있으면 null 리턴
  
• public void push(E e) : 리스트가 나타내는 스택에 요소를 push, 리스트 맨 앞에 요소 추가
  
• public E pop() : 리스트가 나타내는 스택에 요소를 pop, 리스트 맨 앞에 요소를 제거하고 리턴
  
• public boolean removeFirstOccurrence(Object o) : 리스트에 처음으로 나오는 특정 요소 삭제 (head에서 tail로 목록 이동할 때), 요소가 없으면 변경없음
• public boolean removeLastOccurrence(Object o) : 리스트에 마지막에 나오는 특정 요소 삭제 (head에서 tail로 목록 이동할 때), 요소가 없으면 변경없음
  
• public ListIterator listIterator(int index) : 리스트의 특정 위치부터 반복되는 반복자를 리턴
  
• public Iterator descendingIterator() : 반복자를 역의 순서로 리턴 (tail에서 head 순으로 요소 리턴)
  
• public Object clone() : 리스트의 얕은 복사를 리턴
  
• public Object[] toArray() : 모든 요소를 담고 있는 배열을 적절한 순서로 리턴 (처음부터 마지막 요소 순으로)
  
• public T[] toArray(T[] a) : 모든 요소를 담고 있는 배열을 적절한 순서로 리턴 (처음부터 마지막 요소 순으로)
  
• public Spliterator spliterator() : 리스트의 요소에 대해late-binding과 fail-fast Spliterator를 만듬

6. Iterator 알고가기

• Iterator은 자바의 컬렉션 프레임워크에서 컬렉션에 저장되어 있는 요소들을 읽어오는 방법을 표준화 한 것이다.
• 컬렉션 프레임워크란? 데이터를 저장하는 클래스들을 표준화한 설계이다. 
• 컬렉션 프레임워크는 아래 그림과 같이 데이터를 저장하는 구조에 따라 3가지 인터페이스로 구성된다.

https://hwan1001.tistory.com/10 참고

[JAVA] Collection(List, Set, Map)의 종류와 이해

가. Iterator의 메소드

• hasNext() : 읽어올 요소가 남아있는지 확인하는 메소드, 요소가 있다면 true, 없다면 false
• next() : 다음 데이터를 반환한다.
• remove() : next()로 읽어론 요소를 삭제한다.
• 메소드의 호출 순서는 hasNext() -> next() -> remove() 이다.

7. LinkedList를 활용한 게임 만들기

가. 게임설명

1 2 3 4 5 6 7 8 9

0 0 0 0 0 0 0 0 0

 

0 1 3 5 7 10 11 12 13 14

1 1 1 1 1  0   0   0  0  0

 

0 5 11 14 15 16 17 18 19 20

2 2  1   1  0   0   0  0   0  0

                 .

                 .

                 .               

import java.util.LinkedList;
import java.util.Scanner;
 
// < 게임설명 >
// 랜덤함수 rand()를 이용해 0이나 1을 밖에 삭제하거나 유지한다.
// 유지 될 때는 아래의 count값을 처음에는 0으로 들어가지만 유지 될 때마다 1씩 추가해 준다.
// 그리고 크기는 10개로 유지하되 삭제한 경우에는 10부터 들어 갈 수 있도록 프로그램을 작성
// 키보드를 입력받아 계속해서 출력되도록 프로그램 작성
// 99가 출력이 되면 게임이 종료된다.
 
class Pair {
    int num;
    int count;
    
    public Pair(int num, int count) {
        this.num = num;
        this.count = count;
    }
    
    void outout_num() {
        System.out.printf("%3d", num);
    }
    void outout_count() {
        System.out.printf("%3d", count);
    }
}
 
// 링크드 리스트 사용
public class Ex05 {
    public static void main(String[] args) {
        LinkedList<Pair> arr_list = new LinkedList<Pair>();
        int input = 0;
        int num = 0;
 
        Scanner scan = new Scanner(System.in);
        
        while(true) {
            System.out.print("키보드 입력(99는 종료) : ");
            input = scan.nextInt();
            
            if(input == 99)
                break;
            
            //int rand = (int)(Math.random()*2) % 2;
            //System.out.println(rand);
            // 갱신 : 죽이느냐 살리느냐, 또한 카운트를 위한 for문
            // 그럴러면 LinkedList를 사용해야 된다.
            // size() 만큼 도세요.
            // 랜덤 하게 제거 rand()
 
            for(int i = 0 ; i < arr_list.size() ; ++i) {
                int rand = (int)(Math.random()*2) % 2;
                
                arr_list.get(i).count++;
                //1이면 제거
                if(rand == 1) {
                    arr_list.remove(i--);
                }
            }
            
            int size = arr_list.size();
            // 생성, new를 통한 list.add()
            // 위에서 제거 된 만큼 생성
            for(int j = 0 ; j < 10-size ; ++j) {
                    arr_list.add(new Pair(num++, 0));
            }
            
            // 출력문
            for (Pair item : arr_list) {
                item.outout_num();
            }System.out.println();
            for (Pair item : arr_list) {
                item.outout_count();
            }System.out.println();
        }
    }
}
 

 

2019.07.22(월) [LinkedList Project(LinkedList 함수 사용 예제)] [Test05-Ex05 Project(게임)]