Android what is linked list

Linked List in Java

Jun 11, 2017 · 5 min read

A linked list is a data structure that consists of a group of nodes representing a sequence together. Each node includes a piece of data, in this example we’ll use numbers, and they contain a reference to the next node in the list. For example, let’s look at the difference between an array of numbers, and a linked list with nodes containing the same number data.

In an array each element has no re l ation to the other, and in Java the size of an array is not dynamic. For a linked list, we can solve both of those problems. By writing a Node class, we can store a given value and a reference to a following Node. This would allow us the ability to dynamically add elements and traverse through them. To write the Node class, we can create two constructors, one where we don’t know the next Node and the other where we do. It will also be helpful down the road to create getter and setter methods:

The second class we need to create is the Linked List class. One thing I have learned from the HackerRank 30 Days of Code challenge is to always think about three basic goals when writing a new class:

• What are the properties of this class?
• How to write the constructor(s)?
• What methods do I need to write?

Each linked list has a node at the head(or a null node at the head) so we’re going to want that, and then it’s going to be helpful to keep track of the length of the linked list, creating an integer “count”. For our constructors, we want to be able to create a linked list with a node and without one. In terms of the methods that we will need, the goal is to be able to implement the following:

• Ability to add nodes
• Ability to remove nodes
• How many nodes in this sequence?
• Is the sequence empty?
• Get data from a specified node

With that, here is a the basic skeleton of a linked list class:

This is how I implemented each method:

In order to add a node to the linked list, we have to iterate through the linked list until we reach a node that has a null next value. Our getters and setters we wrote earlier are extremely useful here. When we first start the method, we begin at the head, assigning the variable current to head. We then create a new node called temp, with addNode’s parameter “value” as the parameter for temp. From there we check first if the head is null and we have an empty linked list. If this is the case, the head becomes assigned to temp and we return out of the method. In case that head is not null, we want to reach the end of the linked list and change the final node’s next value from null to temp.

Removing a node takes big O(N), as we have to traverse through the end of the Linked List, deleting the final item from the chain. Once the last item is deleted by eliminating the current node’s reference point, you would decrement the count of the linked list.

getCount() and isEmpty()

These are both pretty straightforward. getCount() acts as a getter method for the count property, and isEmpty checks if count is zero.

Our final method is to retrieve the value of a given node. The one tricky part about this one is we’re not counting from 0 in the for loop, being that we’re not saying there’s a 0th node. If a node less than or equal to 0 gets inputted, we’re returning -1. If we have a valid node, then with a for loop we’re going to traverse the Linked List, assigning a Node current to the Node we are looking for.

With our methods written, we can put together some driver code to test it.

While we could have easily called the built in LinkedList class from Java, now we know what’s going on underneath the hood. Thanks for reading, keep on Linking and Listing!

Источник

Структуры данных в картинках. LinkedList

Приветствую вас, хабражители!

Продолжаю начатое, а именно, пытаюсь рассказать (с применением визуальных образов) о том как реализованы некоторые структуры данных в Java.

В прошлый раз мы говорили об ArrayList, сегодня присматриваемся к LinkedList.

LinkedList — реализует интерфейс List. Является представителем двунаправленного списка, где каждый элемент структуры содержит указатели на предыдущий и следующий элементы. Итератор поддерживает обход в обе стороны. Реализует методы получения, удаления и вставки в начало, середину и конец списка. Позволяет добавлять любые элементы в том числе и null.

Создание объекта

Footprint
Object size: 48 bytes

Только что созданный объект list, содержит свойства header и size.

header — псевдо-элемент списка. Его значение всегда равно null, a свойства next и prev всегда указывают на первый и последний элемент списка соответственно. Так как на данный момент список еще пуст, свойства next и prev указывают сами на себя (т.е. на элемент header). Размер списка size равен 0.

Добавление элементов

Footprint
Object size: 112 bytes

Добавление элемента в конец списка с помощью методом add(value), addLast(value)
и добавление в начало списка с помощью addFirst(value) выполняется за время O(1).

Внутри класса LinkedList существует static inner класс Entry, с помощью которого создаются новые элементы.

Каждый раз при добавлении нового элемента, по сути выполняется два шага:

1) создается новый новый экземпляр класса Entry

2) переопределяются указатели на предыдущий и следующий элемент

Добавим еще один элемент

Добавление элементов в «середину» списка

Для того чтобы добавить элемент на определенную позицию в списке, необходимо вызвать метод add(index, value). Отличие от add(value) состоит в определении элемента перед которым будет производиться вставка

Метод entry(index) пробегает по всему списку в поисках элемента с указанным индексом. Направление обхода определяется условием (index > 1)). По факту получается что для нахождения нужного элемента перебирается не больше половины списка, но с точки зрения асимптотического анализа время на поиск растет линейно — O(n).

Как видно, разработчик может словить IndexOutOfBoundsException, если указанный индекс окажется отрицательным или большим текущего значения size. Это справедливо для всех методов где в параметрах фигурирует индекс.

Удаление элементов

Удалять элементы из списка можно несколькими способами:
— из начала или конца списка с помощью removeFirst(), removeLast() за время O(1);
— по индексу remove(index) и по значению remove(value) за время O(n).

Рассмотрим удаление по значению

Footprint
Object size: 176 bytes

Внутри метода remove(value) просматриваются все элементы списка в поисках нужного. Удален будет лишь первый найденный элемент.

В общем, удаление из списка можно условно разбить на 3 шага:

1) поиск первого элемента с соответствующим значением

2) переопределяются указатели на предыдущий и следующий элемент

3) удаление указателей на другие элементы и предание забвению самого элемента

Итераторы

Для собственноручного перебора элементов можно воспользоваться «встроенным» итератором. Сильно углубляться не буду, процессы протекающие внутри, очень похожи на то что описано выше.

Приведенный выше код поместит указатель в начало списка. Так же можно начать перебор элементов с определенного места, для этого нужно передать индекс в метод listIterator(index). В случае, если необходимо начать обход с конца списка, можно воспользоваться методом descendingIterator().

Стоит помнить, что ListIterator свалится с ConcurrentModificationException, если после создания итератора, список был изменен не через собственные методы итератора.

Ну и на всякий случай примитивный пример перебора элементов:

Итоги

— Из LinkedList можно организовать стэк, очередь, или двойную очередь, со временем доступа O(1);
— На вставку и удаление из середины списка, получение элемента по индексу или значению потребуется линейное время O(n). Однако, на добавление и удаление из середины списка, используя ListIterator.add() и ListIterator.remove(), потребуется O(1);
— Позволяет добавлять любые значения в том числе и null. Для хранения примитивных типов использует соответствующие классы-оберки;
— Не синхронизирован.

Ссылки

Объем занимаемой памяти измерялся с помощью инструмента memory-measurer. Для его использования также понадобится Guava (Google Core Libraries).

Источник

Linked List Data Structure

A linked list is a linear data structure, in which the elements are not stored at contiguous memory locations. The elements in a linked list are linked using pointers as shown in the below image:

In simple words, a linked list consists of nodes where each node contains a data field and a reference(link) to the next node in the list.

Topics :

Circular Linked List :

Geeksforgeeks Courses:

1. Language Foundation Courses [C++ / JAVA / Python ]
Learn any programming language from scratch and understand all its fundamentals concepts for a strong programming foundation in the easiest possible manner with help of GeeksforGeeks Language Foundation Courses – Java Foundation | Python Foundation | C++ Foundation

2. Geeks Classes Live
Get interview-centric live online classes on Data Structure and Algorithms from any geographical location to learn and master DSA concepts for enhancing your problem-solving & programming skills and to crack the interview of any product-based company – Geeks Classes: Live Session

3. Complete Interview Preparation
Get fulfilled all your interview preparation needs at a single place with the Complete Interview Preparation Course that provides you all the required stuff to prepare for any product-based, service-based, or start-up company at the most affordable prices.

4. DSA Self Paced
Start learning Data Structures and Algorithms to prepare for the interviews of top IT giants like Microsoft, Amazon, Adobe, etc. with DSA Self-Paced Course where you will get to learn and master DSA from basic to advanced level and that too at your own pace and convenience.

5. Company Specific Courses – Amazon, Microsoft, TCS & Wipro
Crack the interview of any product-based giant company by specifically preparing with the questions that these companies usually ask in their coding interview round. Refer GeeksforGeeks Company Specific Courses: Amazon SDE Test Series, etc.

Please write comments if you find anything incorrect, or you want to share more information about the topic discussed above.

Источник

Android what is linked list

Linked List is a type of Linear Data Structure that is second mostly used data structure after array, which allocates memory dynamically at run time that is it doesn’t require any size initialization as in case of array.

LinkedList stores data in the forms of nodes, which is divided into two parts, first part stores the data and second part points to the next node by storing the address of that node.

In this way it forms a chain of nodes as shown in figure 1.

We have first node which contains Data and Address to next node, and similarly second and third node forming a chain.

Important Note: To create code, pattern required is:

LinkedList linkedList=new LinkedList ();

Table of Contents

Example Of LinkedList:

Program for simple insertion in linked list:

Output:

Description about program: Here to insert the element in linked list first of all just create the linked list using LinkedList linkedList=new LinkedList (); This will create an empty linked list of String type for you. Here linkedlist is name of created list. Now for insertion in this, just make use add method already given java.util.LinkedList. simply pass the object in the argument to which you want to add in this. After that an iterator is created which is given in java.util.Iterator. this iterator will move in list from first to last with single move directly.

Types of Linked List:

Following are the types of Linked List:

1. Singly Linked List:

In Singly linked list node contains data part and address of only forward node. In this type of data structure nodes can be traversed only in forward direction.

2. Doubly Linked List:

In doubly Link List node contains three part, first part contains address of previous node, second part contains the data and the third node contains address of forward node. In this type of data structure nodes can be traversed in both directions that is forward as well as backward.

3. Circular Linked List:

Circular Linked list is similar to singly link list , only difference is last node of the list points to the first node, that is last node contains the address of first node, forming a circular chain.

LinkedList Methods In JAVA:

Let us discuss all the LinkedList methods one by one with Examples in Java.

1. void add(int index, Object element):

This method adds element of Specific Object type at the specified index of the Linked List as mentioned the method. If in case the index specified is out of range it throws an IndexOutOfBounds Exception. Example of this method is shown below:

Output:

2. boolean add(Object o):

It adds an element of Specific Object type at the end of Linked List . It gives True if element is successfully added, and gives false if it is not. Example of this method is shown below:

Output :

3. boolean addAll(Collection c):

This method adds each element of the given collection at the end of the Linked List, It returns True if collection is added successfully, and returns false if it is not. If the collection passed is null then Null Pointer Exception is thrown. Example of this method is shown below:

Output:

Basic operations that can be performed on Linked List:

1. Insertion:

To add an Element at the beginning of the linked list.

2. Deletion:

To delete an Element from the beginning of the linked list.

3. Display:

To display all the elements of the linked list.

4. Search:

To search a node from the whole given linked list.

5. Delete:

To delete a particular node from the linked list.

Program to insert element from user defined class in linked list

Output:

Description about the program: In the above program, a class LinkedListHelp is created in which info and node are taken to represent the content of listnode. And in main class its objects are created and after that they were added to linkedlist one by one and printed using an iterator. Method used here is same as in first program.

Program to add content of one list to other using addAll() method

Output:

Description about the program: Here in the above program two different list were created using concept of class and different objects were added into both the lists. And then by using special method addAll content of second list were appended into first list. The syntax used for appending in the list is linkedList.addAll(linkedList2);where linkedlist is variable name representing the first list, addAll is method used for appending the elements and linkedlist2 is name for second list which is appended.

Program to insert inbetween, FirstPostion and LastPosition using Add(indexOf, object), addFirst, addLast methods in the linked list

Output:

Description about the program: As from the output its much clear what is happening in this program. But for better understanding it is important to know how its occurring. Like if want to insert an element in between the list there is method used add(index, elementtoadd). This method can be used used to add object at any particular index of given list. If you have to insert the element at firstpsoition which is termed as firstnode of list simple addFirst() method is called. Using this element will be added at firstposition in the list. And if you have to add the element at last position method used is addLast(). This method simply insert the element at last position in the given list.

Источник