Shulou(Shulou.com)06/03 Report--

This article introduces how the linear structure linked list of data structure in web development, the content is very detailed, interested friends can refer to, hope to be helpful to you.

I. Preface

The linked list we are going to talk about today is different. The linked list is not only a focus of our data structure learning, but also a difficulty. Why is the linked list so important? Because it is the simplest and truly dynamic data structure.

Second, why linked lists are important

Linked list is a real dynamic data structure.

The simplest dynamic data structure

A deeper understanding of references (or pointers)

A deeper understanding of recursion

Auxiliary composition of other data structures

More in-depth understanding of references (or pointers): related to memory, although you do not have to manage memory manually in java, a deeper understanding of linked lists as a data structure can help you to have a deeper understanding of references, pointers, and even many topics related to memory management in computer systems.

More in-depth understanding of recursion: linked lists also have a very clear recursive structure, and because linked lists are data structures, we can have a deeper understanding of recursion, which is not available.

The linked list itself is also functional: auxiliary composition of other data structures (hashMap, stack, and queue)

What is a linked list

Linked list is a kind of data structure in which nodes record memory addresses and link each other to form a chain of storage. Compared with arrays, linked lists do not need continuous regions in memory, but only need each node to record the memory address of the next node and find it through references, which makes the operation time of adding and deleting linked lists very small, while searching traversing time consumes a lot.

The LinkedList we use in Java every day is a two-way linked list. On the other hand, the linked list is realized by its basic component unit node (Node). Most of the linked lists we see in daily life are single and double linked lists.

Cell node (Node):

Class Node {E e; Node next;}

E is a linked list element

Next refers to the next node of the current node

To the linked list, it is like our train. Each node is actually a carriage. We store the real data in the car, and there is a connection between the car and the car, so that our data is integrated, and users can easily query or other operations on all the data. Then the data and data connection is completed by this next.

Of course, linked lists cannot be endless. If the next of a node is Null, it means that this node is the last node. This is the linked list.

The following figure is shown (single linked list):

Advantages of linked lists: truly dynamic, no need to deal with fixed capacity problems; disadvantages of linked lists: loss of random access

In the array: each index takes out the corresponding element of the index directly from the array, this is because from the underlying mechanism, the space opened up by the array is continuously distributed in memory, so we can directly find the offset of this array and directly calculate the memory address stored in this data, which can be used directly.

Linked list: while the linked list is connected by Next layer by layer, we need to use this Next to find the elements we need to take out.

4. Create our own linked list 4.1 basic linked list structure / * inner class of the underlying linked list * @ param * / public class LinkedList {/ / Design private inner classes, so that users do not need to know the underlying implementation of the linked list, / / do not need to know the node node, and shield the underlying implementation of the coding implementation, private class Node {public E e; public Node next. / / public can operate public Node (E this.e Node next) {this.e = e; this.next = next;} public Node (E) {this (e < null);} public Node () {this (null,null) at will on LinkedList. @ Override public String toString () {return e.toString ();}

Inner class Node: design a private inner class that does not need to know the underlying implementation of the linked list or the node node, and shields the underlying implementation of the user's coding implementation e: element next: a reference to Node

4.2 add elements

We were talking about how to add elements to an array, and it's very convenient for us to add elements to the end of the array, because it's sequential for the array, and what's interesting is that for the linked list, on the contrary, it's very convenient to add elements to the head of the chain. In fact, it's very easy to understand. For the array, we have the variable size, which points directly to the next position of the last element in the array. That is, the position of the next element to be added, so it is very easy to add directly, because there is the variable size, which tracks the tail of the array. For the linked list, we set up a header head of the linked list, but there is no variable to track the tail of the linked list, so it is very convenient for us to add elements to the head of the linked list. The most important things are node.next = head and head = node, as shown in the following figure:

4.2.1 chain header add element

Code implementation: / / add elements to the chain header e public void addFirst (E) {/ / Mode 1 / / Node node = new Node (e); / / node.next = head; / / head = node; / / Mode 2 head = new Node (eMagin head); size + +;} 4.2.2 add elements in the middle of the linked list

We need to add element 666 at index 2, we just need to find the node (1) before element 666 to insert, we call it prev, then point the (1) next of the previous node to 666, and then point this node of 666 to the node (2) after the previous node (1), and the whole insertion is completed, in which the key codes are node.next=prev.next and prev.next=node. The key: we need to find the previous node where the node was added.

Code implementation: / / add a new element e public void add (int index,E e) {if (index) to the index (0-based) position of the linked list

< 0 || index >

Size) throw new IllegalArgumentException ("Add failed. Illegal index."); if (index = = 0) addFirst (e); else {Node prev = head; for (int I = 0; I

< index - 1; i++) {//将prev 放入下一个节点，直到移动到index - 1 prev = prev.next; //方式一 // Node node = new Node(e); // node.next = prev.next; // prev.next = node; //方式二 prev.next = new Node(e,prev.next); size++; } } } //在链表末尾添加新的元素e public void addLast(E e){ add(size,e); }4.2.3 添加操作时间复杂度 4.3 为链表设计虚拟头结点 上面我们介绍了链表的添加操作，那么我们在添加的时候遇到了一个问题，就是在链表任意一个地方的时候，添加一个元素，在链表头添加一个元素，和在链表其他地方添加元素，逻辑上会有差别，为什么在链表头添加元素会比较特殊呢，因为我们在链表添加元素的过程，要找到待添加的 之前的一个节点，但是由于对于链表头没有之前的一个节点，不过我们可以自己创建一个头结点，这个头节点就是 虚拟头结点，这个节点对于用户来说是不存在， 用户也不会感知到这个节点的存在，我们是屏蔽了这个节点的存在，如下图所示： 代码实现：private Node dummyHead; int size; public LinkedList(){ dummyHead = new Node(null,null); size = 0; } //获取链表中的元素个数 public int getSize(){ return size; } //返回链表是否为空 public boolean isEmpty(){ return size == 0; } //在链表的index(0-based)位置添加新的元素e public void add(int index,E e){ if(index < 0 || index >

Size) throw new IllegalArgumentException ("Add failed. Illegal index."); Node prev = dummyHead; for (int I = 0; I

< index; i++) prev = prev.next; prev.next = new Node(e,prev.next); size ++; } //在链表头中添加元素e public void addFirst(E e){ add(0,e); } //在链表末尾添加新的元素e public void addLast(E e){ add(size,e); }4.4 链表元素 get、set、是否存在操作//在链表的index(0-based)位置添加新的元素e public E get(int index){ if(index < 0 || index >

Size) throw new IllegalArgumentException ("Get failed. Illegal index."); Node cur = dummyHead.next; for (int I = 0; I

< index; i++) cur = cur.next; return cur.e; } //获得链表的第一个元素 public E getFirst(){ return get(0); } //获取链表的最后一个元素 public E getLast(){ return get(size - 1); } //在链表的index(0-based)位置添加新的元素e public void set(int index,E e){ if(index < 0 || index >

Size) throw new IllegalArgumentException ("Set failed. Illegal index."); Node cur = dummyHead.next; for (int I = 0; I

< index; i++) cur = cur.next; cur.e = e; } //查找链表中是否有元素e public boolean contains(E e){ Node cur = dummyHead.next; while (cur != null){ if(cur.e.equals(e)) return true; cur = cur.next; } return false; }4.5.1 修改和查找操作时间复杂度

4.5 deleting linked list elements

To add the element where we want to delete the index (2), we need to find a location before the node to be deleted, that is, (1). We use prev to indicate that after finding this node, then (2) is the index we need to delete. We call it delNode, as shown in the following figure:

Code implementation: / / delete the element at Index (0-based) position from the linked list, and return the deleted element public E remove (int index) {if (index)

< 0 || index >

Size) throw new IllegalArgumentException ("Remove failed. Illegal index."); Node prev = dummyHead; for (int I = 0; I

< index; i++) prev = prev.next; Node retNode = prev.next; prev.next = retNode.next; retNode.next = null; size --; return retNode.e; } //从链表中删除第一个位置的元素 public E removeFirst(){ return remove(0); } //从链表中删除最后一个位置的元素 public E removeLast(){ return remove(size - 1); }4.5.1 删除操作时间复杂度 4.6 完整代码/** * 底层链表的内部类 * @param */ public class LinkedList { private class Node{ public E e; public Node next;//public 可以在LinkedList随意操作 public Node(E e,Node next){ this.e = e; this.next = next; } public Node(E e){ this(e,null); } public Node(){ this(null,null); } @Override public String toString() { return e.toString(); } } private Node dummyHead; int size; public LinkedList(){ dummyHead = new Node(null,null); size = 0; } //获取链表中的元素个数 public int getSize(){ return size; } //返回链表是否为空 public boolean isEmpty(){ return size == 0; } //在链表头中添加元素e public void addFirst(E e){ //方式一 // Node node = new Node(e); // node.next = head; // head = node; //方式二 add(0,e); } //在链表的index(0-based)位置添加新的元素e public void add(int index,E e){ if(index < 0 || index >

Size) throw new IllegalArgumentException ("Add failed. Illegal index."); Node prev = dummyHead; for (int I = 0; I

< index; i++) prev = prev.next; prev.next = new Node(e,prev.next); size ++; } //在链表末尾添加新的元素e public void addLast(E e){ add(size,e); } //在链表的index(0-based)位置添加新的元素e public E get(int index){ if(index < 0 || index >

Size) throw new IllegalArgumentException ("Get failed. Illegal index."); Node cur = dummyHead.next; for (int I = 0; I

< index; i++) cur = cur.next; return cur.e; } //获得链表的第一个元素 public E getFirst(){ return get(0); } //获取链表的最后一个元素 public E getLast(){ return get(size - 1); } //在链表的index(0-based)位置添加新的元素e public void set(int index,E e){ if(index < 0 || index >

Size) throw new IllegalArgumentException ("Set failed. Illegal index."); Node cur = dummyHead.next; for (int I = 0; I

< index; i++) cur = cur.next; cur.e = e; } //查找链表中是否有元素e public boolean contains(E e){ Node cur = dummyHead.next; while (cur != null){ if(cur.e.equals(e)) return true; cur = cur.next; } return false; } //从链表中删除Index(0-based)位置的元素，返回删除的元素 public E remove(int index){ if(index < 0 || index >

Size) throw new IllegalArgumentException ("Remove failed. Illegal index."); Node prev = dummyHead; for (int I = 0; I

< index; i++) prev = prev.next; Node retNode = prev.next; prev.next = retNode.next; retNode.next = null; size --; return retNode.e; } //从链表中删除第一个位置的元素 public E removeFirst(){ return remove(0); } //从链表中删除最后一个位置的元素 public E removeLast(){ return remove(size - 1); } @Override public String toString() { StringBuilder res = new StringBuilder(); for (Node cur = dummyHead.next;cur != null; cur= cur.next) res.append(cur + "->

"); res.append (" Null "); return res.toString ();}} 4.2.7 result Test: public static void main (String [] args) {LinkedList linkedList = new LinkedList (); / / add element 0-4 for (int I = 0; I)

< 5 ; i++) { linkedList.addFirst(i); System.out.println(linkedList); } //添加第二个元素添加 666 linkedList.add(2,666); System.out.println(linkedList); //删除第二个元素 666 linkedList.remove(2); System.out.println(linkedList); //删除第一个元素 linkedList.removeFirst(); System.out.println(linkedList); //删除最后一个元素 linkedList.removeLast(); System.out.println(linkedList); }打印结果：0->

Null 1-> 0-> Null 2-> 1-> 0-> Null 3-> 2-> 1-> 0-> Null 4-> 3-> 2-> 1-> 0-> Null 4-> 3-> 666-> 2-> 1-> 0-> Null 4-> 3-> 2-> 1-> 0-> Null 3-> 2-> 1-> 0-> Null 3-> 2-> 1-> Null 4.

For addition and deletion, if you are operating on the chain header, it is O (1) level complexity, and the same is true for queries.

5. Linked list application 5.1 implements linked list 5.1.1 interface class using stack: / * @ program: Data-Structures * @ ClassName Stack * @ description: * @ author: lyy * @ create: 2019-11-20 21:51 * @ Version 1.0 * * / public interface Stack {int getSize (); boolean isEmpty (); void push (E); E pop (); E peek () } 5.1.2 implementation class: import com.lyy.datasty.Mystack.Stack; / / linked table stack implements public class LinkedListStack implements Stack {private LinkedList1 list; public LinkedListStack () {list = new LinkedList1 ();} @ Override public int getSize () {return list.getSize ();} @ Override public boolean isEmpty () {return list.isEmpty () } @ Override public void push (E e) {list.addFirst (e);} @ Override public E pop () {return list.removeFirst ();} @ Override public E peek () {return list.getFirst ();} @ Override public String toString () {StringBuilder res = new StringBuilder () Res.append ("Stack:top"); res.append (list); return res.toString ();}} 5.1.3 result: public static void main (String [] args) {LinkedListStack stack = new LinkedListStack (); for (int I = 0; I)

< 5; i++) { stack.push(i); System.out.println(stack); } stack.pop(); System.out.println(stack); }5.1.4 结果打印：Stack：top 0->

Null Stack:top 1-> 0-> Null Stack:top 2-> 1-> 0-> Null Stack:top 3-> 2-> 1-> 0-> Null Stack:top 4-> 3-> 2-> 1-> 0-> Null Stack:top 3-> 2-> 1-> 0-> Null5.2 uses linked lists to implement queue 5.2.1 interface classes / * * @ program: Data-Structures * @ ClassName Queue * @ description: * @ author: lyy * @ create: 2019-11-21 21:54 * @ Version 1.0 * * / public interface Queue {int getSize () Boolean isEmpty (); void enqueue (E e); E dequeue (); E getFront ();} 5.2.2 implementation class public class LinkedListQueue implements Queue {/ / Design a private inner class, so that users do not need to know the underlying implementation of the linked list, / / do not need to know the node node, and mask the underlying implementation of the coding implementation private class Node {public E e; public Node next / / public can operate public Node (E e, Node next) {this.e = e; this.next = next;} public Node (E e) {this (eline null);} public Node () {this (null,null) at will on LinkedList. } @ Override public String toString () {return e.toString ();}} private Node head,tail; private int size; public LinkedListQueue () {head = null; tail = null; size = 0;} @ Override public int getSize () {return size } @ Override public boolean isEmpty () {return size = = 0;} @ Override public void enqueue (E) {if (tail = = null) {tail = new Node (e); head = tail;} else {tail.next = new Node (e); tail = tail.next;} size + + } @ Override public E dequeue () {if (isEmpty ()) throw new IllegalArgumentException ("Cannot dequeue from an empty queue."); Node retNode = head; head = head.next; retNode.next = null; if (head = = null) tail = null; size -; return retNode.e } @ Override public E getFront () {if (isEmpty ()) throw new IllegalArgumentException ("queue is empty."); return head.e;} @ Override public String toString () {StringBuilder res = new StringBuilder (); res.append ("Queue:front"); Node cur = head While (cur! = null) {res.append (cur + "- >"); cur = cur.next;} res.append ("Null tail"); return res.toString ();} 5.2.2 Test class public static void main (String [] args) {LinkedListQueue queue = new LinkedListQueue (); for (int I = 0; I

< 10; i++) { queue.enqueue(i); System.out.println(queue); if(i % 3 ==2){ queue.dequeue(); System.out.println(queue); } } }打印结果：Queue：front 0->

Null tail Queue:front 0-> 1-> Null tail Queue:front 0-> 1-> 2-> Null tail Queue:front 1-> 2-> 3-> 4-> Null tail Queue:front 1-> 2-> 3-> 4-> Null tail Queue:front 2-> 3-> 4-> 5-> Null tail Queue:front 2-> 3-> 4-> 5-> 6-> Null tail Queue:front 2-> 3-> 4-> 5-> 6-> Null tail Queue:front 2-- > 3-> 4-> 5-> 6-> 7-> 8-> Null tail Queue:front 3-> 4-> 5-> 6-> 7-> 8-> Null tail Queue:front 3-> 4-> 5-> 6-> 7-> 8-> 9-> Null tail 6, More linked list structure 6.1 double linked list

Code: class Node {E e; Node next,prev;} 6.1 Loop list

Code: class Node {E e; Node next,prev;}

In java, the underlying LinkedList uses a circular linked list, that is, a circular two-way linked list.

On the development of web data structure linear structure linked list is how to share here, I hope the above content can be of some help to you, can learn more knowledge. If you think the article is good, you can share it for more people to see.

Welcome to subscribe "Shulou Technology Information " to get latest news, interesting things and hot topics in the IT industry, and controls the hottest and latest Internet news, technology news and IT industry trends.