linked list java linked list implementation java examples
이 자습서에서는 Java의 링크 된 목록 데이터 구조가 무엇이며 Java 링크 된 목록을 생성, 초기화, 구현, 트래버스, 반전 및 정렬하는 방법에 대해 설명합니다.
Java에서 LinkedList는 인접하지 않은 위치에 요소를 저장하는 데이터 구조입니다. 선형 데이터 구조입니다.
각 데이터 항목을 '노드'라고하며 각 노드에는 데이터 부분과 주소 부분이 있습니다. 주소 부분은 LinkedList의 다음 노드에 대한 링크를 저장합니다.
=> 모두를위한 Java 교육 시리즈를 보려면 여기를 방문하십시오.
학습 내용 :
Java의 LinkedList
아래는 LinkedList의 일반적인 레이아웃입니다.
위의 LinkedList 표현에서 볼 수 있듯이 LinkedList의 각 항목은“Node”입니다. 각 노드에는 두 부분이 있으며 첫 번째 부분은 데이터를 저장하고 두 번째 부분에는 LinkedList의 다음 노드에 대한 참조 또는 포인터 또는 주소가 있습니다.
임시 가짜 이메일 주소 만들기
LinkedList의 데이터는 Array와 달리 인접하지 않은 위치에 저장되므로 이러한 배열이 필요합니다.
LinkedList의 'Head'는 LinkedList의 첫 번째 요소 주소를 포함하는 포인터입니다. LinkedList의 마지막 노드는 꼬리입니다. 위 그림과 같이 LinkedList에서 마지막 노드의 주소 부분은 LinkedList의 끝을 나타내는 'Null'로 설정되어 있습니다.
위의 다이어그램은 ' 단일 연결 목록 ”는 LinkedList에서 다음 노드의 주소 만 저장합니다.
'로 알려진 다른 버전이 있습니다. 이중 연결 목록 ”각 노드에는 다음 세 부분이 있습니다.
- LinkedList의 이전 요소에 대한 주소 또는 참조 또는 포인터입니다.
- 데이터 부분
- LinkedList의 다음 요소에 대한 주소 또는 참조 또는 포인터입니다.
LinkedList의 첫 번째 요소의 이전 주소는 Null로 설정되고 LinkedList의 Last 요소의 다음 포인터는 Null로 설정됩니다.
이중 연결 목록 표시 :
위의 표현에서 볼 수 있듯이 이중 연결 목록의 각 노드에는 이전 및 다음 노드에 대한 포인터가 있습니다 (따라서 화살표없이 표시됨). 첫 번째 노드의 이전 포인터는 널을 가리키고 마지막 노드의 다음 포인터는 널을 가리 킵니다.
이 LinkedList 자습서에서는 대부분 단일 연결 목록을 다룰 것입니다. 다음 튜토리얼에서 이중 연결 목록에 대해 논의 할 것입니다.
Java LinkedList 클래스
Java에서 연결 목록은 ' LinkedList ' 수업. 이 클래스는 ' java.util ”패키지. LinkedList 클래스는 List 및 Deque 인터페이스를 구현하고 AbstractList 클래스를 상속합니다.
다음은 LinkedList 클래스의 클래스 계층 구조입니다.
위의 다이어그램은 LinkedList 클래스의 계층 구조를 보여줍니다. 표시된대로 LinkedList 클래스는 List 및 Deque 인터페이스를 구현합니다.
이미 언급했듯이 LinkedList 클래스는“ java.util ”패키지. 따라서 프로그램에 다음 명령문 중 하나를 포함하여 프로그램에서 LinkedList 클래스를 사용할 수 있어야합니다.
import java.util.*;또는
import java.util.LinkedList;따라서 위의 계층 구조를 기반으로 LinkedList 클래스의 일반적인 정의는 다음과 같습니다.
public class LinkedList extends AbstractSequentialList implements List, Deque, Cloneable, Serializable다음은 기억해야 할 LinkedList 클래스의 몇 가지 특성입니다.
- 이 클래스는 동기화되지 않습니다.
- 중복 값을 허용합니다.
- 게재 신청서를 유지합니다.
- 이동 중에 요소를 이동할 필요가 없으므로 요소 조작이 더 빠릅니다.
- 이 클래스는 스택, 큐 및 목록을 구현하는 데 사용할 수 있습니다.
Java에서 연결된 목록을 만드는 방법
Java에서 연결 목록을 만들기 전에 먼저 Java에서 연결 목록 노드에 대해 살펴 보겠습니다.
이미 논의했듯이 연결 목록은 노드로 구성됩니다. 따라서 Java에서는 LinkedList를 Node를 별도의 클래스로 사용하는 클래스로 나타낼 수 있습니다. 따라서이 클래스는 Node 유형에 대한 참조를 갖게됩니다.
다음과 같이 표시됩니다.
class LinkedList { Node head; // list head //node - linkedlist class Node { int data; Node next; Node(int d) { data = d; } //constructor to create a new node } } LinkedList 유형의 객체를 만들려면 다음과 같은 두 가지 주요 생성자가 있습니다.
# 1) LinkedList ()
이 생성자의 일반 구문은 다음과 같습니다.
LinkedList linkedList = new LinkedList();위의 문은 빈 LinkedList를 만듭니다.
예를 들면
LinkedList l_list = new LinkedList();그러면 l_list라는 빈 연결 목록이 생성됩니다.
# 2) LinkedList (컬렉션 c)
일반적인 구문은 다음과 같습니다.
LinkedList linkedList = new LinkedList (Collection c);위의 문은 컬렉션 c의 요소를 초기 요소로 사용하여 LinkedList를 만듭니다.
이미 본 다른 목록 데이터 구조와 마찬가지로 연결된 목록은 add 메서드 인 Arrays.asList () 메서드를 사용하거나 컬렉션과 함께 생성자를 인수로 사용하여 초기화 할 수도 있습니다.
자바에서 연결된 목록 구현
다음은 Java의 LinkedList 데이터 구조에 대한 간단한 예입니다. 이 구현 예에서는 add 메서드와 asList 메서드를 사용하여 LinkedList 개체를 초기화합니다.
import java.util.*; public class Main{ public static void main(String() args) { //create a LinkedList object and initialize it with Array elements converted to list LinkedList intList = new LinkedList<>(Arrays.asList(10,20,30,40,50)); //print the LinkedList just created System.out.println('Contents of first LinkedList: ' + intList); //create an empty list LinkedList colorsList = new LinkedList<>(); //add elements to the linkedList using add method. colorsList.add('Red'); colorsList.add('Green'); colorsList.add('Blue'); colorsList.add('Cyan'); colorsList.add('Magenta'); // print the LinkedList System.out.println('
Contents of second LinkedList: ' + colorsList); } } 산출:
첫 번째 LinkedList의 내용 : (10, 20, 30, 40, 50)
두 번째 LinkedList의 내용 : (Red, Green, Blue, Cyan, Magenta)
위의 프로그램은 LinkedList의 생성 및 초기화를 보여줍니다. 먼저, Integer 유형의 LinkedList를 만들고 LinkedList의 초기 값으로 asList 메서드를 사용하여 목록으로 변환 된 Integer 배열을 제공합니다.
다음으로 String 유형의 빈 LinkedList를 만든 다음 add 메서드를 사용하여 LinkedList에 값을 추가합니다.
마지막으로 LinkedList 객체를 모두 문자열로 표시합니다.
자바에서 링크 된 목록 트래버스 / 인쇄
내용을 인쇄하거나 LinkedList의 요소에 대한 작업을 수행하려면 해당 요소를 탐색해야합니다. 우리는 이전 튜토리얼에서 이미 이러한 방법을 보았습니다. 이 섹션에서는 LinkedList와 관련하여 각각의 예를 설명합니다.
for 루프 사용
import java.util.LinkedList; class Main { public static void main(String() args) { // Create a LinkedList and initialize it LinkedList colorList = new LinkedList<>(); colorList.add('Red'); colorList.add('Green'); colorList.add('Blue'); // Using for loop,print the contents of the LinkedList System.out.println('LinkedList elements using for loop:'); for(int i=0; i 산출:
for 루프를 사용하는 LinkedList 요소 :
레드 그린 블루
forEach 루프 사용
import java.util.LinkedList; class Main { public static void main(String() args) { // Create a LinkedList and initialize it LinkedList colorList = new LinkedList<>(); colorList.add('Red'); colorList.add('Green'); colorList.add('Blue'); // Using forEach loop,print the contents of the LinkedList System.out.println('LinkedList elements using forEach loop:'); for(String color:colorList) { System.out.print(color + ' '); } } } 산출:
forEach 루프를 사용하는 LinkedList 요소 :
레드 그린 블루
반복자 사용
import java.util.*; public class Main{ public static void main(String args()){ //declare a LinkedList object LinkedList l_list=new LinkedList(); //Add elements to LinkedList l_list.add('Red'); l_list.add('Green'); l_list.add('Blue'); l_list.add('Yellow'); //declare an iterator for the LinkedList Iterator itr=l_list.iterator(); System.out.println('The contents of Linked List:'); //Iterate through the LinkedList using Iterator and print its elements while(itr.hasNext()){ System.out.print(itr.next() + ' '); } } } 산출:
링크 된 목록의 내용 :
빨간색 녹색 파란색 노란색
컴퓨터 운영 체제 란?
LinkedList 메서드
LinkedList 클래스는 Linked List를 조작하기위한 다양한 메소드를 지원하는 API를 제공합니다. 아래 LinkedList API의 메서드를 표로 정리했습니다.
다음 섹션에서 주요 작업 / 방법에 대해 설명합니다.
방법 원기 기술 맑은 무효 클리어 () 목록에서 모든 요소를 삭제합니다. 더하다 부울 더하기 (E e) LinkedList에 지정된 요소 추가 void add (int 인덱스, E 요소) LinkedList의 지정된 색인에 요소 추가 모두 추가 boolean addAll (콜렉션 c) LinkedList의 끝에 지정된 컬렉션 c의 요소를 추가합니다. 부울 addAll (int index, Collection c) LinkedList의 지정된 인덱스에 지정된 컬렉션 c의 요소를 추가합니다. addFirst 무효 addFirst (E e) LinkedList에 지정된 요소를 첫 번째 요소로 추가합니다. addLast 무효 addLast (E e) 목록 끝에 주어진 요소를 추가합니다. 복제 개체 복제 () LinkedList의 얕은 복사본을 만듭니다. 포함 부울 포함 (Object o) 목록에 지정된 요소가 포함되어 있는지 확인합니다. 그렇다면 true를 반환합니다. 내림차순 반복자 내림차순 Iterator () LinkedList에 대해 역순으로 정렬 된 반복기를 반환합니다. 요소 E 요소 () 목록의 선두에있는 요소를 반환합니다. 가져 오기 E get (int 인덱스) 지정된 인덱스의 요소를 가져옵니다. getFirst E getFirst () LinkedList의 첫 번째 요소를 검색합니다. getLast E getLast () LinkedList의 마지막 요소를 검색합니다. indexOf Int indexOf (객체 o) 목록에서 주어진 요소가 처음 나타나는 색인을 찾아 색인을 반환합니다. 요소를 찾을 수없는 경우 -1. lastIndexOf Int lastIndexOf (객체 o) LinkedList에서 주어진 요소의 마지막 발생 위치를 반환합니다. 주어진 요소가없는 경우 -1 listIterator ListIterator listIterator (int 인덱스) 연결된 목록의 지정된 인덱스에서 listIterator를 반환합니다. 제공 부울 오퍼 (E e) LinkedList의 마지막 요소 (꼬리)로 지정된 요소를 추가합니다. offerFirst 부울 offerFirst (E e) LinkedList의 첫 번째 요소로 지정된 요소를 추가합니다. offerLast 부울 offerLast (E e) LinkedList의 끝에 주어진 요소 e를 추가합니다. 몰래 엿보다 E 엿보기 () 목록을 제거하지 않고 목록의 헤드를 반환합니다. peekFirst E peekFirst () 목록의 첫 번째 요소를 반환합니다. 목록이 비어 있으면 null을 반환합니다. peekLast E peekLast () 마지막 요소를 반환하거나 목록이 비어 있으면 null을 반환합니다. 요소는 삭제되지 않습니다. 투표 E 투표 () LinkedList의 헤드를 반환하고 제거합니다. pollFirst E pollFirst () 목록의 첫 번째 요소를 반환하고 삭제합니다. 목록이 비어 있으면 null을 반환합니다. pollLast E pollLast () 목록의 마지막 요소를 반환하고 삭제합니다. 목록이 비어 있으면 null을 반환합니다. 팝 E 팝 () LinkedList의 스택 표현에서 요소를 팝합니다. 푸시 공허 밀기 (E e) LinkedList의 스택 표현에 요소를 푸시하거나 삽입합니다. 없애다 E 제거 () LinkedList의 헤드를 제거하고 반환합니다. E 제거 (int 인덱스) LinkedList에서 지정된 인덱스의 요소를 삭제합니다. 부울 제거 (Object o) LinkedList에서 지정된 요소의 첫 번째 발생을 삭제합니다. removeFirst E removeFirst () 목록에서 첫 번째 요소를 반환하고 삭제합니다. removeFirstOccurence 부울 removeFirstOccurrence (객체 o) 목록이 머리에서 꼬리로 순회 될 때 목록에서 주어진 요소의 첫 번째 발생을 삭제합니다. removeLast E removeLast () LinkedList의 마지막 요소를 반환하고 삭제합니다. removeLastOccurence 부울 removeLastOccurrence (Object o) 머리에서 꼬리로 이동할 때 LinkedList에서 주어진 요소의 마지막 발생을 제거합니다. 세트 E 세트 (int 인덱스, E 요소) 주어진 인덱스에 주어진 요소를 설정합니다. 현재 요소를 새 요소로 바꿉니다. 크기 Int 크기 () LinkedList의 요소 수 또는 크기를 반환합니다. toArray Object () toArray () LinkedList를 적절한 순서로 모든 목록 요소를 포함하는 배열로 변환합니다. T () toArray (T () a) LinkedList를 인수 a와 동일한 런타임 유형의 배열로 변환합니다.
아래 Java 프로그램은 위에 나열된 다양한 방법을 보여줍니다.
import java.util.*; public class Main { public static void main(String args()) { //create a linked list LinkedList l_list = new LinkedList(); // Add elements to linkedList using various add methods l_list.add('B'); l_list.add('C'); l_list.addLast('G'); l_list.addFirst('A'); l_list.add(3, 'D'); l_list.add('E'); l_list.add('F'); //print the linkedList System.out.println('Linked list : ' + l_list); //Create and initialize an ArrayList ArrayList aList = new ArrayList<>(); aList.add('H'); aList.add('I'); //add the ArrayList to linkedList using addAll method l_list.addAll(aList); //print the linkedList System.out.println('Linked list after adding ArrayList contents: ' + l_list); // use various remove methods to remove elements from linkedList l_list.remove('B'); l_list.remove(3); l_list.removeFirst(); l_list.removeLast(); //print the altered list System.out.println('Linked list after deletion: ' + l_list); // use contains method to check for an element in the linkedList boolean ret_value = l_list.contains('G'); //print the results of contains method if(ret_value) System.out.println('List contains the element 'G' '); else System.out.println('List doesn't contain the element 'G''); // use size methods to return Number of elements in the linked list int size = l_list.size(); System.out.println('Size of linked list = ' + size); // Get and set elements from linked list Object element = l_list.get(3); System.out.println('Element returned by get() : ' + element); l_list.set(3, 'J'); System.out.println('Linked list after change : ' + l_list); //convert linkedList to Array using toArray methods String () list_array = l_list.toArray(new String(l_list.size())); System.out.println('Array obtained from linked List:' + Arrays.toString(list_array)); } } 산출:
연결 목록 : (A, B, C, D, G, E, F)
ArrayList 콘텐츠 추가 후 연결된 목록 : (A, B, C, D, G, E, F, H, I)
삭제 후 연결 목록 : (C, D, E, F, H)
목록에 'G'요소가 없습니다.
연결 목록의 크기 = 5
get ()에 의해 반환 된 요소 : F
변경 후 연결 목록 : (C, D, E, J, H)
연결된 목록에서 얻은 배열 : (C, D, E, J, H)
위 프로그램은 LinkedList 클래스의 다양한 메소드를 보여줍니다. 먼저, String 유형의 LinkedList를 선언합니다. 그런 다음 add, andFirst, addLast, addAll 등과 같은 다양한 버전의 add 메서드를 사용하여 LinkedList를 값으로 채 웁니다.
여기에서 목록의 끝에 직접 요소를 추가하거나 목록의 지정된 위치에 요소를 추가 할 수 있습니다.
또한 addFirst 메서드를 사용하여 목록의 시작 부분에 요소를 추가하고 addLast를 사용하여 목록 끝에 요소를 추가합니다. 그런 다음 remove, removeFirst, removeLast 등과 같은 LinkedList에서 제거 작업을 수행합니다.
remove 메서드의 경우 제거 할 요소를 지정하거나 요소가 제거 될 LinkedList에서 인덱스 또는 위치를 지정할 수 있습니다. removeFirst 및 removeLast 메서드는 목록에서 각각 첫 번째 및 마지막 요소를 제거합니다.
그런 다음 contains 메소드를 사용하여 목록에서 특정 요소를 검색합니다. 다음으로 size () 메서드를 사용하여 LinkedList의 크기 또는 길이를 검색합니다. 그런 다음 get / set 메서드를 사용하여 목록의 특정 인덱스에서 값을 검색 한 다음 목록의 지정된 위치에서 값을 바꿉니다.
마지막으로 toArray 메서드를 사용하여 LinkedList를 Array로 변환합니다.
자바의 역방향 링크 목록
Java에서 연결 목록을 되돌리려면 목록에 대해 역 반복기를 반환하는 'descendingIterator ()'메서드를 사용합니다. 그런 다음이 반복기를 사용하여 목록 및 표시 요소를 탐색 할 수 있습니다.
아래 프로그램은 DescendingIterator () 메서드를 사용하여 연결된 목록을 반전합니다.
import java.util.*; public class Main{ public static void main(String args()){ //create a LinkedList object LinkedList l_list=new LinkedList(); l_list.add('Pune'); l_list.add('Mumbai'); l_list.add('Nagpur'); System.out.println('Linked List : ' + l_list); System.out.println('Linked List in reverse order:'); //use descendingIterator method to get a reverse iterator Iterator iter=l_list.descendingIterator(); //traverse the list using iterator and print the elements. while(iter.hasNext()) { System.out.print(iter.next() + ' '); } } } 산출:
링크 된 목록 : (Pune, Mumbai, Nagpur)
역순으로 연결된 목록 :
Nagpur Mumbai 푸네
위의 프로그램에서 연결 목록을 선언하고 인쇄합니다. 그런 다음 역방향 반복기를 얻은 다음이를 사용하여 목록을 단계별로 살펴보고 각 요소를 표시합니다. 출력에는 링크 된 목록 내용이 표시되며, 먼저 요소가 추가 된 순서대로 출력 된 다음 역순으로 내용이 표시됩니다.
Java에서 연결된 목록 정렬
LinkedList 클래스 개체는 Collections.sort () 메서드를 사용하여 정렬 할 수 있습니다. 이 방법은 비교기를 사용하거나 사용하지 않고 두 가지 버전을 제공합니다. 비교기없이 Collections.sort () 메서드를 호출하면 컬렉션이 자연스러운 순서로 정렬됩니다.
때 비교기 이 메서드와 함께 사용되는 경우 compareTo 메서드를 재정 의하여 자체 정렬 기준을 정의 할 수 있습니다.
아래 Java 프로그램은 Collections.sort ()를 사용하여 LinkedList를 정렬합니다. 여기에서는 자연 순서와 비교기를 사용하여 배열을 정렬합니다.
import java.util.*; public class Main{ public static void main(String args()) { // create and initialize the LinkedList object LinkedList l_list = new LinkedList<>(); l_list.add('Jan'); l_list.add('Feb'); l_list.add('Mar'); l_list.add('Apr'); l_list.add('May'); l_list.add('Jun'); //print original unsorted linkedlist System.out.println('Original LinkedList (unsorted): ' + l_list); // sort LinkedList with Collecitons.sort() method in natural order Collections.sort(l_list); System.out.println('
LinkedList (sorted in natural order): ' + l_list); // sort LinkedList using Collection.sort() and Comparator in Java Collections.sort(l_list, new Comparator() { @Override public int compare(String s1, String s2) { return s1.length() - s2.length(); } } ); System.out.println('LinkedList (sorted using Comparator): ' + l_list); } } 산출:
원본 링크 목록 (정렬되지 않음) : (1 월, 2 월, 3 월, 4 월, 5 월, 6 월)
LinkedList (자연 순서로 정렬 됨) : (4 월, 2 월, 1 월, 6 월, 3 월, 5 월)
LinkedList (비교기를 사용하여 정렬 됨) : (4 월, 2 월, 1 월, 6 월, 3 월, 5 월)
중복 제거
중복 항목을 제거하려면 각 노드를 순회하고 다음 노드와 비교해야합니다. 두 노드가 동일하면 한 노드를 건너 뛰고 다음 노드로 이동합니다.
이런 식으로 각 노드를 순회하고 중복 노드를 제거한 후 중복 요소가없는 결과 목록을 얻습니다.
다음은 중복을 제거하는 Java 프로그램입니다.
class LinkedList_Duplicate { //A class to represent node in linkedlist class Node{ int data; Node next; public Node(int data) { this.data = data; this.next = null; } } //Initially the head and tail of the linked list set to null public Node head = null; public Node tail = null; //add a new node to the linkedlist public void addNode(int data) { //Create new node Node newNode = new Node(data); //If list is empty set head and tail to new node if(head == null) { head = newNode; tail = newNode; } else { // add newNode after the tail tail.next = newNode; //newNode is now the tail or last element tail = newNode; } } //scans the linkedlist and removes duplicate nodes public void removeDuplicateNodes() { //Head is the current node Node current = head, index = null, temp = null; //head = null means list is empty if(head == null) { return; } //traverse through the list else { while(current != null){ //temp node points to previous node to index. temp = current; //Index will point to node next to current index = current.next; while(index != null) { //Check if current node's data is equal to index node's data if(current.data == index.data) { //since node is duplicate skip index and point to next node temp.next = index.next; } else { //Temp will point to previous node of index. temp = index; } index = index.next; } current = current.next; } } } //print the linked list public void print() { //Node current will point to head Node current = head; if(head == null) { System.out.println('List is empty'); return; } while(current != null) { //Print each node by incrementing pointer System.out.print(current.data + ' '); current = current.next; } System.out.println(); } }class Main{ public static void main(String() args) { LinkedList_Duplicate l_List = new LinkedList_Duplicate(); //Add data to the list l_List.addNode(1); l_List.addNode(1); l_List.addNode(2); l_List.addNode(3); l_List.addNode(5); l_List.addNode(2); l_List.addNode(1); l_List.addNode(1); //print the original list System.out.println('Original Linkedlist: '); l_List.print(); //Removes duplicate nodes l_List.removeDuplicateNodes(); //print the altered list without duplicates System.out.println('LinkedList after removing duplicates: '); l_List.print(); } } 산출:
원본 링크 목록 :
1 1 2 3 5 2 1 1
중복 제거 후 LinkedList :
1 2 3 5
위의 프로그램에서 중복을 제거하기 위해 생성 된 연결 목록 클래스가 있습니다. 또한 각 노드를 정의하는 클래스가 있습니다. 즉, 목록의 노드는이 클래스 노드의 객체입니다. 연결 목록에 노드를 추가하는 방법이 있습니다.
그런 다음 removeDuplicate 메서드에서 헤드에서 시작하여 연결된 목록의 각 노드를 탐색하고 중복 된 각 후속 노드를 비교합니다. 중복이 발견되면 해당 노드를 건너 뛰고 다음 노드로 진행합니다.
이렇게하면 중복 노드를 건너 뛰어 ist가 빌드되고 변경된 목록이 print () 메서드를 사용하여 인쇄됩니다.
자바의 순환 연결 목록
순환 연결 목록은 꼬리 또는 마지막 노드가 헤드 또는 첫 번째 노드에 다시 연결된 목록입니다.
아래 다이어그램은 Java의 순환 링크 목록을 보여줍니다.
위의 다이어그램에서 볼 수 있듯이 마지막 노드의 주소 부분 또는 연결 목록의 꼬리는 null로 설정되지 않습니다. 대신 목록의 첫 번째 노드 또는 헤드를 다시 가리켜 순환 연결 목록을 형성합니다.
아래 프로그램은 연결 목록의 개별 노드를 조작해야하는 순환 연결 목록을 구현합니다.
class CircularLinkedList { //Node definition for circular linked list public class Node{ int data; Node next; public Node(int data) { this.data = data; } } //Initially head and tail pointers point to null public Node head = null; public Node tail = null; //add new node to the circular linked list public void add(int data){ //Create new node Node newNode = new Node(data); //check if list is empty if(head == null) { //head and tail point to same node if list is empty head = newNode; tail = newNode; newNode.next = head; } else { //tail points to new node if list is not empty tail.next = newNode; //New node becomes new tail. tail = newNode; //tail points back to head tail.next = head; } } //Display the nodes in circular linked list public void displayList() { Node current = head; if(head == null) { System.out.println('The List is empty'); } else { System.out.println('Circular linked list nodes: '); do{ //Print each node of the linked list System.out.print(current.data + ' '); current = current.next; }while(current != head); System.out.println(); } } } class Main{ public static void main(String() args) { //create a CircularLinkedList object CircularLinkedList c_list = new CircularLinkedList(); //Add data to the list c_list.add(10); c_list.add(20); c_list.add(30); c_list.add(40); //Display the nodes in circular linked list c_list.displayList(); } } 산출:
순환 연결 목록 노드 :
10 20 30 40
자바 8 LinkedList
Java 8의 LinkedList 클래스에 특별히 추가 된 기능은 더 이상 없지만 여전히 데이터를 조작하는 스트림을 도입했습니다.
아래 프로그램은 LinkedList를 표시하기 위해 Java 8 스트림을 사용하는 방법을 보여줍니다.
import java.util.LinkedList; import java.util.List; public class Main { public static void main(String() args) { //create a LinkedList and initialize it to values List colorsList = new LinkedList<>(); colorsList.add('Red'); colorsList.add('Green'); colorsList.add('Blue'); colorsList.add('Cyan'); colorsList.add('Magenta'); //convert List to stream & print it System.out.println('The contents of LinkedList:'); colorsList.stream().forEach(System.out::println); } } 산출:
LinkedList의 내용 :
그물
초록
푸른
청록색
마젠타
자주 묻는 질문
Q # 1) Java에서 Linked List는 언제 사용됩니까?
대답: 수정 작업에서 ArrayList와 같은 컬렉션보다 빠르기 때문에 잦은 추가 / 삭제 작업이 필요한 응용 프로그램에서 사용해야합니다. 대부분 읽기 전용 데이터가있는 응용 프로그램의 경우 ArrayList 또는 유사한 컬렉션을 사용할 수 있습니다.
질문 # 2) ListNode는 무엇입니까?
대답: ListNode는 Java에서 연결된 목록과 관련된 기본 클래스이며 단일 요소 또는 노드와 관련된 정보를 나타냅니다. 각 ListNode는 데이터와 다음 요소에 대한 포인터 또는 참조로 구성됩니다.
질문 # 3) 연결된 목록이 null 값을 허용합니까?
대답: 예, 연결된 목록은 임의의 수의 null 값을 허용합니다.
질문 # 4) 연결된 목록의 장점은 무엇입니까?
답변 : 몇 가지 장점은 다음과 같습니다.
- 추가, 삭제와 같은 조작 작업이 더 빠릅니다.
- 연결된 목록에 대해 메모리를 미리 할당 할 필요가 없으므로 효율적인 메모리 활용이 가능합니다.
- 메모리에 대한 추가 오버 헤드없이 더 빠른 액세스 시간을 제공하며 일정한 시간에 확장 할 수 있습니다.
- 동적 데이터 구조입니다.
- 추가 또는 삭제 된 값에 따라 런타임에 증가 및 축소됩니다.
질문 # 5) 연결 목록의 적용은 무엇입니까?
답변 : 주로 다음 애플리케이션에서 사용됩니다.
- MS-Word, Photoshop 등과 같은 소프트웨어에서 '실행 취소'기능을 구현합니다.
- 스택 및 큐와 같은 데이터 구조를 구현합니다.
- 연결 목록을 사용하여 그래프를 구현할 수도 있습니다.
- 버킷 해싱의 경우 각 버킷을 연결 목록으로 구현할 수 있습니다.
문 # 6) 연결된 목록의 제한 사항은 무엇입니까?
답변 : 몇 가지 제한 사항은 다음과 같습니다.
숙련자를위한 성능 테스트 인터뷰 질문
- 각 노드의 다음 요소에 대한 참조를 보유하는 추가 포인터를 사용하면 사용되는 메모리가 배열보다 훨씬 많습니다.
- 이것은 엄격하게 순차적으로 액세스되는 데이터 구조이므로 연결 목록의 노드는 항상 처음부터 읽어야합니다.
- 특히 단일 연결 목록을 뒤로 탐색하는 것은 어렵습니다.
- 노드가 인접하지 않은 위치에 저장되기 때문에 액세스에 필요한 시간이 길어질 수 있습니다.
결론
이 자습서에서는 기본 연결 목록 데이터 구조를 배웠습니다. 그런 다음 Java에서 제공하는 java.util.LinkedList 클래스로 이동했습니다. 생성자, 메서드 등을 포함하여이 클래스에 대해 자세히 설명했습니다.
또한 정렬, 목록 반전, 중복 제거, 순환 연결 목록 등과 같은 연결된 목록과 관련된 몇 가지 특수 작업에 대해 논의했습니다.
다음 자습서에서는 이중 연결 목록의 특정 기능에 대해 설명합니다.
=> 여기에서 전체 Java 교육 가이드를 확인하십시오.
추천 도서
