연결리스트

연결리스트 또는 링크드리스트(linked list)란 리스트 구현의 한 방법으로 일정한 순서를 가지는 자료들의 저장과 탐색을 효과적으로 관리하기 위하여 각 데이터 요소들에 이전데이터나 다음데이터를 가리키는 참조를 추가적으로 부여하여 자료들을 연결하는 자료구조를 말한다.

역사

연결리스트는 1955~1956년에 랜드 연구소에서 앨런 뉴웰, 클리프 셔, 허버트 A. 사이먼이 그들의 정보 처리 언어(IPL)를 위한 1차 자료 구조로서 개발하였다.

개요

각 자료는 이전 데이터나 다음 데이터에 대한 참조를 가져야 하므로 연결리스트에 저장되는 데이터는 원본 데이터와 다른 데이터에 대한 참조를 표현한 구조여야 하며 이를 노드(node)라고 부른다. 연결리스트는 각 노드가 데이터와 포인터를 가지고 한 줄로 연결되어 있는 방식의 자료구조이다. 데이터를 담고 있는 노드들이 연결되어 있고, 노드의 포인터가 이전, 다음노드와의 연결을 담당한다.

연결리스트

연결리스트 사용법

연결리스트 선언

LinkedList에서는 초기의 크기를 미리 생성할수는 없다. LinkedList를 생성할 때 사용 타입을 명시해야 한다.

 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) 함수를 사용하게 되면 마지막에 데이터가 추가된다.

 LinkedList<Integer> list = new LinkedList<Integer>();
  list.addFirst(1);  //가장 앞에 데이터 추가
  list.addLast(2);  //가장 뒤에 데이터 추가
  list.add(3);  //데이터 추가
  list.add(1, 4);  //index 1뒤에 데이터 4 추가 

LinkedList 값 추가

연결리스트 값 삭제

LinkedList에 값을 제거하는 방법도 값을 추가하는 방법과 유사하다. removeFirst()메소드를 사용하면 가장 첫 데이터가 삭제되고 removeLast()를 사용하면 가장 뒤에 있는 데이터가 삭제된다. remove(index,value)를 사용하여 특정 값을 제거 할수도 있다. 모든 값을 제거하려면 clear 메소드를 사용하면 된다.

 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의 크기를 구하려면 LinkedList의 size() 메소드를 사용하면 된다.

 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 메소드보다 속도가 느리다.

 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을 리턴한다.

 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

구성

연결리스트의 종류에는 3가지가 있다. 단일 연결리스트, 이중 연결리스트, 원형 연결리스트이다.

단일 연결리스트

단일 연결리스트(Singly Linked List)는 데이터 각 노드가 다음 노드에 대해서만 참조하는 가장 단순한 형태의 연결리스트이다. 하지만 이러한 특성 때문에, 데이터 탐색중에 한번 지나친 node(노드)를 찾으려면 다시 head(헤드)부터 탐색을 해야 한다.

 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 추가

새로운 노드를 생성하고 헤드를 가리키도록 변경 그 후에 헤드가 노드를 가리키도록 수정하면, 맨앞에 노드가 생성된 것처럼 보인다.

맨 앞에 node 추가

• addAtTail(val) : node를 마지막에 추가

리스트의 마지막 노드를 먼저 찾고, 마지막 노드가 생성한 노드를 가리키도록 한다.

node를 마지막에 추가

• addAtIndex(index, val) : index에 node를 추가

특정 인덱스의 노드(current)와 그 이전 노드(previous)를 찾는다. 새로운 노드를 생성하고 (prev)가 새로운 노드를 가리키고, 새로운 노드가 (cur)를 가리키도록 한다.

index에 node를 추가

• deleteAtIndex(index) : index의 node를 삭제

특정 인덱스의 노드(current)와 그 이전 노드(previous)를 찾는다. prev가 cur의 다음 노드를 가리키도록 변경한다.

index에 node를 삭제

이중 연결리스트

이중 연결리스트(Doubly Linked List)는 노드와 노드가 양방향으로 연결되어 있기 때문에 탐색하는 방향이 양쪽으로 가능하다는 점이다. 하지만 단일연결리스트에 비해 노드를 지정하기 위한 변수를 하나 더 선언해야 하며 구현이 복잡하다.

 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로 변경해준다.

리스트 맨 앞에 추가

• addAtTail(val) : 리스트 맨 마지막에 추가

리스트의 마지막으로 이동하여 노드를 생성한다. 마지막 노드와 새로운 노드의 prev와 next를 연결해 준다.

리스트 맨 마지막에 추가

• addAtIndex(index, val) : 특정 index에 node 추가

특정 노드(cur)을 찾은뒤 prev노드와 새로 생성한 노드를 연결한뒤 cur노드와 연결시킨다.

특정 index에 node 추가

• deleteAtIndex(index) : 특정 index의 node를 삭제

특정 노드(cur)을 찾은뒤 prev와 next를 연결시키며 cur노드는 삭제된다.

특정 index에 node 삭제

배열과 차이점

배열은 쉽게 구현할 수 있고 빠른 검색기능을 가지고 있지만 저장될 데이터의 수를 가늠하기 어렵거나 삽입과 삭제에 걸리는 시간이 길다. 연결리스트는 배열에 비해서 데이터의 추가/삭제가 용이하나, 인덱스가 없는 리스트의 특징으로 인하여 특정 요소에 접근하기 위해서는 순차 탐색을 필요로 하므로 일반적으로 탐색 속도가 떨어진다 저장될 데이터의 수를 가늠하기 어렵거나 삽입과 삭제에 걸리는 시간. 탐색 또는 정렬을 자주하는 경우엔 배열을 사용하고 데이터의 추가/삭제가 많은 경우 연결리스트를 사용한다.

참고자료

• 연결리스트〈자바 배열과 리스트 비교〉,《개발이 하고 싶어요》, 2014-04-05
• 연결리스트 정의〈연결 리스트 구현하기〉, 《freestrokes》, 2019-04-18
• 연결리스트 사용법〈연결 리스트 사용법〉, 《코딩팩토리》, 2020-05-23
• 단일 연결리스트〈단일 연결리스트〉, 《chacha》, 2020-05-19
• 이중 연결리스트 정의〈이중 연결리스트〉, 《IT에 취.하.개》, 2018-04-19
• 이중 연결리스트〈양방향 연결리스트〉, 《chacha》, 2020-05-21

같이 보기

• 노드
• 자료구조
• 포인터
• 자바
• 배열

이 연결리스트 문서는 데이터에 관한 글로서 검토가 필요합니다. 위키 문서는 누구든지 자유롭게 편집할 수 있습니다. [편집]을 눌러 문서 내용을 검토·수정해 주세요.

개발 : 프로그래밍, 소프트웨어, 데이터 □■⊕, 솔루션, 보안, 하드웨어, 컴퓨터, 사무자동화, 인터넷, 모바일, 사물인터넷, 게임, 메타버스, 디자인 데이터 ACID • CRUD • CSV • DAO • DB • DBMS • DB 명령어 • DCL • DDL • DML • DTO • ERD • ETL • JDBC • LOD • MDM • ODBC • RDBMS • RDF • SQL • 가상 데이터베이스 • 관계형 데이터베이스 • 그래프 • 기본키(PK) • 내부조인 • 널 • 노드 • 다이어그램 • 대리키 • 대체키 • 데이터 • 데이터댐 • 데이터마트 • 데이터 모델링 • 데이터뱅크 • 데이터베이스(DB) • 데이터베이스 언어 • 데이터 사이언스 • 데이터 사전 • 데이터 웨어하우스 • 데이터 정의어(DDL) • 데이터 제어어(DCL) • 데이터 조작어(DML) • 데이터 클러스터 • 데이터 토큰 (문자열) • 데이터 통합 • 덱 • 디비서버 • 라이트조인 • 락 • 레코드 • 레프트조인 • 로그 • 로그파일 • 로깅 • 롤백 • 리두로그 • 릴레이션 • 마스터데이터 • 마스터데이터관리(MDM) • 마이그레이션 • 메타데이터 • 배열 • 뷰 • 빅데이터 • 서브쿼리 • 수퍼키 • 순차리스트 • 스키마 • 스택 • 슬로우쿼리 • 엔티티 • 역정규화 • 연결리스트 • 외래키(FK) • 외부조인 • 인덱스 • 인덱싱 • 인젝션 • 자료구조 • 정규화 • 정보 • 조인 • 커밋 • 쿼리 • 큐 • 키 • 타깃 • 테이블 • 튜플 • 트랜잭션 • 트리 • 트리거 • 티비마이그레이터 • 풀조인 • 프로시저 • 필드 • 해시 • 해시맵 • 해시태그 • 해시테이블 • 해시함수 • 해싱 • 후보키 데이터베이스 관리 시스템 (DBMS) 관계형 데이터베이스 관리 시스템(RDBMS) • 노에스큐엘(NoSQL) • 데이터베이스 관리 시스템(DBMS) • 더비 • 디비투(DB2) • 레디스 • 마리아디비(MariaDB) • 마이에스큐엘(MySQL) • 몽고디비 • 빅테이블 • 사이베이스 • 선디비 • 알티베이스 • 액세스 • 에스큐엘(SQL) • 에스큐엘라이트(SQLite) • 에이치베이스 • 엠에스에스큐엘(MS-SQL) • 오라클(Oracle) • 인터베이스 • 인포믹스 • 카산드라 • 카우치디비 • 큐브리드 • 티베로 • 파이어버드 • 포스트그레스큐엘(PostgreSQL) • 하이퍼테이블 DB 명령어 alter • array • create • delete • drop • from • full join • grant • inner join • insert • join • left join • null • order by • outer join • rename • revoke • right join • select • truncate • update • where 시스템 연계 API • CGI • EAI • ESB • JPA • RSS • SOA • SOAP • SSL • SSO • web3.js • XML • 디비투디비(DB-to-DB) • 레스트풀(RESTful) • 상호운용성 • 시스템 인터페이스 • 신디케이션 API • 오픈 API • 웹 API • 웹개방성 • 윈도우 API • 자바 API • 크롤링 • 프라이빗 API 위키 : 자동차, 교통, 지역, 지도, 산업, 기업, 단체, 업무, 생활, 쇼핑, 블록체인, 암호화폐, 인공지능, 개발, 인물, 행사, 일반