[자료구조] 선형 자료구조 - 연결 리스트

1. 연결 리스트 (Linked List) 란 무엇인가

---

• 노드(객체) 끼리의 주소 포인터를 서로 가리키며 링크(참조) 함으로써 이어지는 구조
• 즉, 데이터를 링크로 연결해서 관리하는 자료구조
• 노드는 데이터 저장 단위로, 값과 포인터로 구성되어 있다.
• 포인터는 다음 노드나 이전 노드의 연결 정보를 담고 있다.

 

 

---

 

2. 연결 리스트 (Linked List) 장점, 단점

(1) 장점

• 데이터 공간을 미리 할당할 필요가 없음 
• 즉, 리스트의 길이가 가변적이라 데이터 추가 / 삭제 용이 (메모리 관리 측면)

 

(2) 단점

• 연결구조를 위한 별도 데이터 공간 필요
• 연결 정보를 찾는 시간이 필요 (접근 속도가 상대적으로 느림)
• 데이터 추가, 삭제 시 앞뒤 데이터의 연결을 재구성 하는 작업 필요

 

 

---

 

 

 

3. 연결 리스트 (Linked List) 기본 연산

(1) 데이터 추가

• 가장 앞에 데이터를 추가

LinkedList<String> list = new LinkedList<>(Arrays.asList("A","B","C"));

list.addFirst("new");   // 가장 앞에 데이터 추가

 

---

 

 

• 중간에 데이터 추가

LinkedList<String> list = new LinkedList(Arrays.asList("A","B","C"));

list.add(1,"new");   // index 1의 위치에 데이터 "new" 추가

 

---

 

• 가장 끝에 추가

LinkedList<String> list = new LinkedList<>(Arrays.asList("A","B","C"));

list.addLast("new");   // 가장 뒤에 데이터 추가

 

 

 

 

 

 

 

addFirst() 와 addLast() 는 요소를 첫번째, 마지막에 추가하는 것이기 때문에 O(1)의 시간이 걸린다.
그러나 중간 삽입일 경우 중간에 삽입할 위치까지의 탐색을 필요로 하기 때문에 O(N)의 시간이 걸린다.

 

---

 

 

 

(2) 데이터 삭제

• 가장 앞 데이터 삭제

LinkedList<String> list = new LinkedList<>(Arrays.asList("A","B","C"));

list.removeFirst();   // 첫 번째 값 제거

 

 

 

---

 

 

• 중간 데이터 삭제

LinkedList<String> list = new LinkedList<>(Arrays.asList("A","B","C"));

list.remove(1);    // index가 1인 위치에 있는 데이터 제거

 

 

 

---

 

 

 

• 가장 끝 데이터 삭제

LinkedList<String> list = new LinkedList<>(Arrays.asList("A","B","C"));

list.removeLast();   // 가장 마지막 데이터 제거

 

---

 

(3) LinkedList 요소 검색

메서드	설명
int size()	LinkedList에 저장된 객체의 개수를 반환
boolean isEmpty()	LinkedList가 비어있는지 확인한다.
boolean contains(Object obj)	지정된 객체(obj)가 LinkedList에 포함되어 있는지 확인한다.
boolean containsAll(Collection c)	지정된 컬렉션의 모든 요소가 포함되었는지 알려준다.
int indexOf(Object obj)	지정된 객체(obj)가 저장된 위치를 찾아 반환한다.
int lastIndexOf(Object obj)	지정된 객체(obj)가 저장된 위치를 뒤에서부터 역방향으로 찾아 반환한다.

 

LinkedList<String> list = new LinkedList<>(Arrays.asList("A","B","C"));

// 해당 값을 가지고 있는 요소 위치를 반환 (앞에서부터 검색)
list.indexOf("B");    // 1

// 해당 값을 가지고 있는 요소 위치를 반환 (뒤에서부터 검색)
list.lastIndexOf("D");     // -1  : 찾고자 하는 값이 없으면


list.add("1");
list.add("2");

//list안에 "1" 값이 있는지 확인
list.contains("1");     // true

 

 

---

 

 

(4) LinkedList 요소 얻기

개별 단일 요소를 얻고자 하면 get 메소드로 얻어올 수 있다. 단, LinkedList는 ArrayList와 달리 만약 100번째 노드를 확인하기 위해서는 첫 번째 노드부터 100번째 노드까지 참조를 일일이 따라서 이동해야 하기 때문에 탐색 성능은 좋지 않은 편이다.

메소드	설명
Object get(int index)	지정된 위치(index)에 저장된 객체를 반환
List subList(int fromIndex, int toIndex)	fromIndex부터 toIndex사이에 저장된 객체를 List로 반환

 

list.get(1);    // 1번째 index 요소의 값 출력

 

 

 

 

 

---

 

 

(4) LinkedList 요소 변경

메소드	설명
Object set(int index, Object obj)	지정한 위치(index)의 객체를 주어진 객체로 변경

 

LinkedList<String> list = new LinkedList<>();
list.add("10");
list.add("20");
list.add("30");

list.set(1,"A");    // index가 1인 위치의 데이터를 문자열 "A"로 변경
System.out.println(list);    // [10, A, 30]

 

 

---

 

 

(5) LinkedList 객체 생성

• LinkedList를 사용하기 위해선 상단에 패키지를 명시하여 가져와야 한다.

import java.util.LinkedList;

LinkedList<Integer> list = new LinkedList<Integer>();  //타입 명시하였으므로 int 타입만 가능

LinkedList<Integer> list2 = new LinkedList<Integer>(Arrays.asList(1,2,3));  // 생성시 초기값 설정

 

 

 

 

 

 

---

 

 

 

4. 연결 리스트 (Linked List) 코드 구현

(1) 노드 클래스 생성

class Node {
	Node next;   //다음 노드 주소를 저장하는 필드
    int data;    //데이터를 저장하는 필드
    Node() {}
    Node(int data, Node next) {
    	this.data = data;
        this.next = next;
    }
}

 

 

---

 

(2) 기본적인 LinkedList Class 코드로 구현하기

 

class LinkedList {

    Node head;

    LinkedList() {}
    LinkedList(Node node) {
        this.head = head;
    }

    //연결 리스트 비어있는지 확인
    public boolean isEmpty() {
        if (this.head == null) {
            return true;
        }
        return false;
    }


    // 연결 리스트의 맨 뒤에 데이터 추가
    public void addData(int data) {
        if(this.head == null) {
            this.head = new Node(data,null);
        } else {
            Node cur = this.head;
            while (cur.next != null) {
                cur = cur.next;
            }
            cur.next = new Node(data,null);
        }
    }


    // 연결 리스트의 맨 뒤의 데이터 삭제
    public void removeData() {
        if (this.isEmpty()) {
            System.out.println("List is empty");
            return;
        }
        Node cur = this.head;
        Node prev = cur;

        while (cur.next != null) {
            prev = cur;
            cur = cur.next;
        }

        if(cur == this.head) {
            this.head = null;
        } else {
            prev.next = null;
        }
    }



    // 연결 리스트에서 데이터 찾기
    public void findData(int data) {
        if (this.isEmpty()) {
            System.out.println("List is empty");
            return;
        }

        Node cur = this.head;
        while(cur.next != null) {
            if(cur.data == data) {
                System.out.println("Data exist!");
                return;
            }
            cur = cur.next;
        }
        System.out.println("Data not found!");

    }



    // 연결 리스트의 모든 데이터 출력
    public void showData() {
        if (this.isEmpty()) {
            System.out.println("List is empty");
            return;
        }

        Node cur = this.head;
        while(cur != null) {
            System.out.println(cur.data + " ");
            cur = cur.next;
        }
        System.out.println();
    }


}