[알고리즘] 자료구조: 링크드 리스트(Linked List)

링크드 리스트 구조(Linked List)

• 연결 리스트라고도 함
• 배열은 순차적으로 연결된 공간에 데이터를 나열하는 데이터 구조
• 링크드 리스트는 떨어진 곳에 존재하는 데이터를 화살표로 연결해서 관리하는 구조
• 링크드 리스트 기본 구조와 용어
  • 노트(Node): 각 데이터 저장 단위(데이터 값, 포인터)로 구성
  • 포인터(pointer): 각 노드 안에서, 다음이나 이전의 노드와의 연결 정보를 가지고 있는 공간

 

링크드 리스트 장단점

• 장점
  • 미리 데이터 공간을 할당하지 않아도 됨
    • 배열은 미리 데이터 공간을 할당해아함
• 단점
  • 연결을 위한 별도 데이터 공간이 필요하므로, 저장공간 효율이 높지 않음
  • 연결 정보를 찾는 시간이 필요하므로 접근 속도가 느림
  • 중간 데이터 삭제 시, 앞뒤 데이터의 연결을 재구성해야 하는 부가적인 작업 필요

 

사용 이유?

 

가장 큰 장점인 리스트의 길이가 가변적이라는 점이다. 배열의 단점을 링크드 리스트가 커버할 수 있다.
배열은 크기가 가변적이지 않다. 우선 크기를 정해준 다음에 모자라면 메모리를 더 할당하고, 배열의 데이터를 복사해야 한다. 오래 걸리고 비효율적이라는 것을 알 수 있다.
하지만 링크드 리스트는 다음 노드만 추가하면 되기 때문에 리스트의 사이즈를 조정하는데, 그리 큰 비용을 들이지 않는다. 단점으로는 어떤 노드를 search 하거나 데이터를 변경할 때 바로 찾아낼 수가 없다.
즉, 데이터가 자주 추가되거나 가변적으로 자주 변하게 될 프로그램이라면 링크드 리스트를 쓰는 것이 좋을 것이고, 주로 데이터의 변경이나 탐색을 위한 것이라면 배열을 쓰는 것이 좋을 것이다.

 

구현

1. 선언

import java.util.LinkedList;

LinkedList numList = new LinkedList();  
// LinkedList<>안에는 String등 다양한 데이터 타입을 선언할 수 있다.

 

2. addFirst(list, data): 링크드 리스트의 새로운 노드를 추가한다. 가장 앞에 새로운 노드를 추가하는 연산이다.

public void addFirst(Object input){  
Node newNode = new Node(input); //노드 생성

newNode.next = head; //새로운 노드의 다음 노드로 헤드를 지정

head = newNode; //head를 새로운 노드로 지정 
size++; 

if(head.next == null)
    tail = head;
}

 

 

3. addLast(list, data): 가장 뒤에 노드를 추가한다.

public void addLast(Object input) {  
Node newNode = new Node(input); //노드 생성
if(size == 0) //리스트의 노드가 없는 경우, 첫번째 노드로 추가하는 메소드 사용 
    addFirst(input); 
else {
    tail.next = newNode; //마지막 노드의 다음 노드로 생성한 노드를 지정
    tail = newNode; //마지막 노드를 갱신 
    size++; 
    }
}

 

 

4.중간에 추가

 

특정 위치의 노드를 찾는 방법

Node node(int index) {  
Node x = head;  
for(int i = 0; i < index; i++)  
x = x.next;  
return x;  
}

public void add(int k, Object input){  
// k = 0이면 첫 번째 노드에 추가하는 것, addFirst 사용  
if(k==0)  
addFirst(input);  
else {  
Node temp1 = node(k-1); //k-1번째 노드를 temp1로 지정  
Node temp2 = temp1.next; //k번째 노드를 temp2로 지정

    Node newNode = new Node(input); 
    temp1.next = newNode; //temp1의 다음 노드로 새로운 노드를 지정
    newNode.next = temp2; //새로운 노드 다음 노드로 temp2 지정
    size++;

    if(newNode.next == null)
        tail = newNode; 
        //새로운 노드의 다음 노드가 없다면
        //새로운 노드가 마지막 노드이기 때문에 
}
}

 

 

5. removeNode(list, data): 링크드 리스트가 갖고 있는 노드 중에 data값을 가지고 있는 노드를 삭제한다.

 

처음 노드 삭제

public Object removeFirst() {  
Node temp = head; //첫번째 노드를 head로 지정  
head = temp.next; //head의 값을 두번째 노드로 변경

Object returnData = temp.data; //데이터 삭제 전 리턴할 값을 임시 변수에 담아둔다.
temp = null;
size--;
return returnData;

}

중간 데이터 삭제

public Object remove(int k) {  
if(k == 0)  
return removeFirst();

Node temp = node(k-1); //k-1번째 node를 temp의 값으로 지정 

Node todoDeleted = temp.next; 
//삭제할 노드를 todoDeleted에 기록
// 삭제 노드를 지금 제거하면 삭제 앞 노드와 삭제 뒤 노드를 연결할 수 없다. 

temp.next = temp.next.next; 
//삭제 앞 노드의 다음 노드로 삭제 뒤 노드를 지정한다. 

Object returnData = todoDeleted.data; 
//삭제된 데이터를 리턴하기 위해서 returnData에 저장한다. 

if(todoDeleted == tail)
    tail = temp;

todoDeleted = null;
size--;
return returnData;
}

 

6. 링크드리스트 크기

System.out.println("size : " + numList.size());  
// → 현재 Linked List의 크기를 보여준다.

 

 

7. 데이터 출력

System.out.println(numList.get(1));  
// → "()"안에 인덱스번호에 해당되는 데이터를 출력한다.

 

 

8. 데이터 검색

System.out.println(numList.contains(1));  
// → 데이터 검색 (없으면 False 반환한다)

System.out.println(numList.indexOf(1));  
// → 해당 데이터가 몇 번째 인덱스에 존재하는 지 확인 (없으면 -1 출력)