해시넷
연결리스트
연결리스트 또는 링크드리스트(linked list)란 리스트 구현의 한 방법으로 일정한 순서를 가지는 자료들의 저장과 탐색을 효과적으로 관리하기 위하여 각 데이터 요소들에 이전데이터나 다음데이터를 가리키는 참조를 추가적으로 부여하여 자료들을 연결하는 자료구조를 말한다.[1]
목차
역사[편집]
연결리스트는 1955~1956년에 랜드 연구소에서 앨런 뉴웰, 클리프 셔, 허버트 A. 사이먼이 그들의 정보 처리 언어(IPL)를 위한 1차 자료 구조로서 개발하였다.
개요[편집]
각 자료는 이전 데이터나 다음 데이터에 대한 참조를 가져야 하므로 연결리스트에 저장되는 데이터는 원본 데이터와 다른 데이터에 대한 참조를 표현한 구조여야 하며 이를 노드(node)라고 부른다.[1] 연결리스트는 각 노드가 데이터와 포인터를 가지고 한 줄로 연결되어 있는 방식의 자료구조이다. 데이터를 담고 있는 노드들이 연결되어 있고, 노드의 포인터가 이전, 다음노드와의 연결을 담당한다.[2]
연결리스트 사용법[편집]
연결리스트 선언[편집]
LinkedList에서는 초기의 크기를 미리 생성할수는 없다. LinkedList를 생성할 때 사용 타입을 명시해야 한다.[3]
LinkedList list = new LinkedList(); //타입 미설정 Object로 선언된다. LinkedList<Student> members = new LinkedList<Student>(); //타입설정 Student객체만 사용가능 LinkedList<Integer> num = new LinkedList<Integer>();//타입설정 int타입만 사용가능 LinkedList<Integer> num2 = new LinkedList<>(); //new에서 타입 파라미터 생략가능 LinkedList<Integer> list2 = new LinkedList<Integer>(Arrays.asList(1,2)); //생성시 값추가
연결리스트 값 추가[편집]
LinkedList에 값을 추가하는 방법은 여러가지가 있지만 대중적으로 add(index, value) 메소드를 사용한다. index를 생략하면 가장 마지막에 있는 데이터가 추가되며, ㅁaddFirst(value) 함수를 사용하게 되면 가장 앞에 있는 헤더의 값이 변경되고 addLast(value) 함수를 사용하게 되면 마지막에 데이터가 추가된다. [3]
LinkedList<Integer> list = new LinkedList<Integer>(); list.addFirst(1); //가장 앞에 데이터 추가 list.addLast(2); //가장 뒤에 데이터 추가 list.add(3); //데이터 추가 list.add(1, 4); //index 1뒤에 데이터 4 추가
연결리스트 값 삭제[편집]
LinkedList에 값을 제거하는 방법도 값을 추가하는 방법과 유사하다. removeFirst()메소드를 사용하면 가장 첫 데이터가 삭제되고 removeLast()를 사용하면 가장 뒤에 있는 데이터가 삭제된다. remove(index,value)를 사용하여 특정 값을 제거 할수도 있다. 모든 값을 제거하려면 clear 메소드를 사용하면 된다. [3]
LinkedList<Integer> list = new LinkedList<Integer>(Arrays.asList(1,2,3,4,5)); list.removeFirst(); //가장 앞의 데이터 제거 list.removeLast(); //가장 뒤의 데이터 제거 list.remove(); //생략시 0번째 index제거 list.remove(1); //index 1 제거 list.clear(); //모든 값 제거
연결리스트 크기 구하기[편집]
LinkedList의 크기를 구하려면 LinkedList의 size() 메소드를 사용하면 된다. [3]
LinkedList<Integer> list = new LinkedList<Integer>(Arrays.asList(1,2,3)); System.out.println(list.size()); //list 크기 : 3
연결리스트 값 출력[편집]
LinkedList의 get 메소드를 사용하면 원하는 index 값이 리턴된다. 전체 출력은 대부분 for문을 통해서 출력 하며, Iterator를 사용해서 출력 할 수도 있다. 메소드 내부의 동작은 순차 탐색으로 이루어져 있어 ArrayList의 get 메소드보다 속도가 느리다. [3]
LinkedList<Integer> list = new LinkedList<Integer>(Arrays.asList(1,2,3));
System.out.println(list.get(0));//0번째 index 출력
for(Integer i : list) { //for문을 통한 전체출력
System.out.println(i);
}
Iterator<Integer> iter = list.iterator(); //Iterator 선언
while(iter.hasNext()){//다음값이 있는지 체크
System.out.println(iter.next()); //값 출력
}
연결리스트 값 검색[편집]
LinkedList에서 찾고자 하는 값을 검색하려면 LinkedList의 contain(value)메소드를 사용한다.
만약 값이 있다면 ture로 리턴되고, 값이 없다면 false가 리턴된다. 값이 있는 index를 찾으려면 indexof(value)메소드를 사용하고 값이 없다면 -1을 리턴한다. [3]
ArrayList<Integer> list = new ArrayList<Integer>(Arrays.asList(1,2,3)); System.out.println(list.contains(1)); //list에 1이 있는지 검색 : true System.out.println(list.indexOf(1)); //1이 있는 index반환 없으면 -1
구성[편집]
연결리스트의 종류에는 2가지가 있다. 단일 연결리스트, 이중 연결리스트이다.
단일 연결리스트[편집]
단일 연결리스트(Singly Linked List)는 데이터 각 노드가 다음 노드에 대해서만 참조하는 가장 단순한 형태의 연결리스트이다. 하지만 이러한 특성 때문에, 데이터 탐색중에 한번 지나친 node(노드)를 찾으려면 다시 head(헤드)부터 탐색을 해야 한다. [4]
class SinglyLinkedNode {
int val; // 변수 val에 데이터가 저장된다.
SinglyLinkedNode next = null; // next는 다음노드를 가리킨다.
SinglyLinkedNode(int v) {
val = v;
}
}
Singly Linked List 클래스에 각 메소드들을 포함하여 구현하면 이런 소스코드가 나온다.
public class MyLinkedList {
private SinglyLinkedNode head = null;
public MyLinkedList() {
}
public int get(int index) { // 인자로 전달되는 index의 데이터를 리턴
}
public void addAtHead(int val) { // node를 리스트의 맨 앞에 추가
}
public void addAtTail(int val) { // node를 리스트 마지막에 추가
}
public void addAtIndex(int index, int val) { // 특정 index에 node를 추가
}
public void deleteAtIndex(int index) { // 특정 index의 node를 삭제
}
}
- addAtHead() : 맨 앞에 node 추가
새로운 노드를 생성하고 헤드를 가리키도록 변경 그 후에 헤드가 노드를 가리키도록 수정하면, 맨앞에 노드가 생성된 것처럼 보인다. [4]
- addAtTail(val) : node를 마지막에 추가
리스트의 마지막 노드를 먼저 찾고, 마지막 노드가 생성한 노드를 가리키도록 한다.[4]
- addAtIndex(index, val) : index에 node를 추가
특정 인덱스의 노드(current)와 그 이전 노드(previous)를 찾는다. 새로운 노드를 생성하고 (prev)가 새로운 노드를 가리키고, 새로운 노드가 (cur)를 가리키도록 한다. [4]
- deleteAtIndex(index) : index의 node를 삭제
특정 인덱스의 노드(current)와 그 이전 노드(previous)를 찾는다. prev가 cur의 다음 노드를 가리키도록 변경한다. [4]
이중 연결리스트[편집]
이중 연결리스트(Doubly Linked List)는 노드와 노드가 양방향으로 연결되어 있기 때문에 탐색하는 방향이 양쪽으로 가능하다는 점이다. 하지만 단일연결리스트에 비해 노드를 지정하기 위한 변수를 하나 더 선언해야 하며 구현이 복잡하다. [5] [6]
class DoublyListNode {
int val;
DoublyListNode next, prev; // next는 다음 노드를, prev는 이전 노드를 가리킨다.
DoublyListNode(int x) {val = x;} // 이중 연결리스트이기 때문에 변수를 2개 설정한다.
}
Doubly Linked List 클래스에 각 메소드들을 포함하여 구현하면 이런 소스코드가 나온다.
class MyLinkedList {
DoublyListNode head = null;
public MyLinkedList() {
}
public int get(int index) {
}
public void addAtHead(int val) {
}
public void addAtTail(int val) {
}
public void addAtIndex(int index, int val) {
}
public void deleteAtIndex(int index) {
}
}
- addAtHead() : 리스트 맨 앞에 추가
새로운 노드를 생성하고 노드의 next와 헤드의 prev를 연결한뒤 head를 node로 변경해준다. [6]
- addAtTail(val) : 리스트 맨 마지막에 추가
리스트의 마지막으로 이동하여 노드를 생성한다. 마지막 노드와 새로운 노드의 prev와 next를 연결해 준다. [6]
- addAtIndex(index, val) : 특정 index에 node 추가
특정 노드(cur)을 찾은뒤 prev노드와 새로 생성한 노드를 연결한뒤 cur노드와 연결시킨다.[6]
- deleteAtIndex(index) : 특정 index의 node를 삭제
특정 노드(cur)을 찾은뒤 prev와 next를 연결시키며 cur노드는 삭제된다.[6]
배열과 차이점[편집]
배열은 쉽게 구현할 수 있고 빠른 검색기능을 가지고 있지만 저장될 데이터의 수를 가늠하기 어렵거나 삽입과 삭제에 걸리는 시간이 길다.[1] 연결리스트는 배열에 비해서 데이터의 추가/삭제가 용이하나, 인덱스가 없는 리스트의 특징으로 인하여 특정 요소에 접근하기 위해서는 순차 탐색을 필요로 하므로 일반적으로 탐색 속도가 떨어진다 저장될 데이터의 수를 가늠하기 어렵거나 삽입과 삭제에 걸리는 시간. 탐색 또는 정렬을 자주하는 경우엔 배열을 사용하고 데이터의 추가/삭제가 많은 경우 연결리스트를 사용한다.[2]
각주[편집]
- ↑ 1.0 1.1 1.2 〈배열과 리스트 비교〉, 《개발이 하고 싶어요》, 2014-04-05
- ↑ 2.0 2.1 〈연결리스트 구현하기〉, 《freestrokes》, 2019-04-18
- ↑ 3.0 3.1 3.2 3.3 3.4 3.5 〈연결리스트 사용법〉, 《코딩팩토리》, 2020-05-23
- ↑ 4.0 4.1 4.2 4.3 4.4 〈단일 연결리스트〉, 《chacha》, 2020-05-19
- ↑ 〈이중 연결리스트〉, 《IT에 취.하.개》, 2018-04-19
- ↑ 6.0 6.1 6.2 6.3 6.4 〈양방향 연결리스트〉, 《chacha》, 2020-05-21
참고자료[편집]
- 연결리스트〈자바 배열과 리스트 비교〉,《개발이 하고 싶어요》, 2014-04-05
- 연결리스트 정의〈연결 리스트 구현하기〉, 《freestrokes》, 2019-04-18
- 연결리스트 사용법〈연결 리스트 사용법〉, 《코딩팩토리》, 2020-05-23
- 단일 연결리스트〈단일 연결리스트〉, 《chacha》, 2020-05-19
- 이중 연결리스트 정의〈이중 연결리스트〉, 《IT에 취.하.개》, 2018-04-19
- 이중 연결리스트〈양방향 연결리스트〉, 《chacha》, 2020-05-21
같이 보기[편집]
