Visible data structure Android version of the double Linked list

Zero, preface,

1. The last article analyzed the single linked list, which is a data structure used to carry data. Each table node is loaded with a data element

2. A double-linked list is where each node holds a reference to the first and last two nodes in addition to the data element 3. In order to unify the operation of nodes, a virtual node is generally added at the beginning and end of the real linked list, which is called head node and tail node 4. If a single LinkedList is a train, then that list is a double-headed reinforced train. This is the structure at the bottom of LinkedList in Java. I hope you can and I at Github together to witness: the birth and growth of DS4Android, welcome to star

1. Retention Town Building: The final operation effect of the double linked list:

2. Introduction to double Linked Lists:

Double linked list is an operation on nodes, which in turn carries data (T). Generally speaking, double linked list operates on nodes so as to operate data (T), just like carriage transportation and acquisition, which is only the carrier. Double linked lists are different from single linked lists in that one Node holds references to both the first and last nodes, making it convenient for both head and tail operations. Node is just an auxiliary tool and is not exposed. It corresponds to the data, and makes the data arranged in chain. Manipulating the nodes is equal to manipulating the data, just like the marionette, rather than directly operating the various limbs of the puppet itself (data T). To unify the operation of nodes, it is common to add a virtual head (headNode) and virtual tail (tileNode) to the front of the list (encapsulated, not exposed).Copy the code

3. Dual linked list implementation: the priority of this article

One, the realization of double linked list structure: LinkedChart

1. The interface of the table is defined inAn array of table articleI won’t put it up here

Here is the LinkedChart after implementing the interface and the implementation of the simple method

/** * Author: Zhang Feng Jiete: <br/> * Time: 2018/11/220022:15:36 <br/> * Email: [email protected]<br/> * Description: */ public class LinkedChart<T> implements IChart<T> {private Node headNode; // Virtual tailNode -- equivalent to head locomotive private Node tailNode; Private int size; // Private int size; Public SingleLinkedChart() {headNode = new Node(null, null, null); TailNode = new Node(headNode, null, null); Next = tailNode; // Instantiate tailNode and point prev to headNode.next = tailNode; // Size = 0; } @override public void add(int index, T el) {} @override public void add(T el) {add(size, el); } @Override public T remove(int index) { return null; } @Override public T remove() { return remove(size); } @Override public int removeEl(T el) { return 0; } @Override public boolean removeEls(T el) { return false; } @Override public void clear() { headNode = new Node(null, null, null); TailNode = new Node(headNode, null, null); Next = tailNode; // Instantiate tailNode and point prev to headNode.next = tailNode; // Size = 0; } @override public T set(int index, T el) {return null; } @Override public T get(int index) { return null; } @Override public int[] getIndex(T el) { return null; } @Override public boolean contains(T el) { return getIndex(el).length ! = 0; } @Override public IChart<T> contact(IChart<T> iChart) { return null; } @Override public IChart<T> contact(int index, IChart<T> iChart) { return null; } @Override public boolean isEmpty() { return size == 0; } @Override public int size() { return size; } @Override public int capacity() { return size; }Copy the code

2. Design of single link Node class:

LinkedChart is the equivalent of a two-headed train. It is very convenient to press it to get the relationship of the cars right first, and then put the train together at the end

Node is used as a private inner class of LinkedChart in order to hide Node, and the resources of LinkedChart can be used, just like the heart is inside the body and invisible to people outside, but it is crucial and can also obtain the information and resources inside the body

A double chain car, at least know what the node.t is,

Which car is next (Node.next) and which car is last (Node.prev)

Private class Node {/** * data */ private T el; /** * private Node prev; /** * private Node next; private Node(Node prev, Node next, T el) { this.el = el; this.prev = prev; this.next = next; }}Copy the code

Second, Node (Node) bottom layer operation (CRUD)—- the heart of the list

1. Query operation: getNode

The single linked list query in the last article: equivalent to looking for cars next to each other in a viewport

A double linked list has two locomotives, which means that they can operate at both ends, so to be as efficient as possible, decide whether the cars are in the front or the back, which is much faster than a single linked list.

/ / private Node<T> getNode(int index) {Node<T> targetNode; / / private Node<T> targetNode; / / declare the target node if (index < 0 | | index > size - 1) {/ / index cross-border processing throw new IndexOutOfBoundsException (); } // If (index < size / 2) {targetNode = headNode.next; for (int i = 0; i < index; i++) { targetNode = targetNode.next; } else {// Find targetNode = tailNode.prev in reverse order if the index is in the last half; for (int i = size - 1; i < index; i++) { targetNode = targetNode.prev; } } return targetNode; }Copy the code

AddNode ()

Or the locomotive: what if I want to insert a T3 car between T0 and T1?

Step 1: Connect the back chain bolt of T0 to T3, and the front chain bolt of T3 to T0 —– complete the connection between T0 and T3. Step 2: Connect the back chain bolt of T3 to T2, and the front chain bolt of T1 to T3 —– complete the connection between T1 and T3

/ / private void addNode(Node target, @param, @param, @param, @param, @param) NewNode = newNode (target.prev, target, el); // newNode (target.prev, target, el); // newNode (target.prev, target, el); Next = newNode; // next points to T3 target.prev.next = newNode; //T1 prev points to T3 target.prev = newNode; // list length +1 size++; }Copy the code

RemoveNode ()

How to delete T1:

It’s simple: T0 and T2 hold hands, and then let T1 go alone…

/** * remove the target Node ** @param target * @return target Node data */ private T removeNode(Node target) {// remove the next Node from the target Node target.prev.next = target.next; Target.next. Prev = target.prev; target.prev = null; Next = null; // Let go of the right hand -- tear away // return target.el; }Copy the code

3. Modify the setNode node

/ / private T setNode(int index, int index, int index, int index, int index, int index, int index, int index, int index, int index, int index, int index, int index T el) { Node node = getNode(index); T tempNode = node.el; node.el = el; return tempNode; }Copy the code

4. Clear: clearNode()

Train of thought and delete the same: the first and last virtual nodes refer to each other, there is no element in the middle, formally, the current list on all delete re-instantiate the head node ——

Re-instantiate the tail node —— the tail of the train said: the old niang start (null), do not take you to play, so the locomotive and the tail of the train, hand in hand, toward the distance…

/** * clear all nodes */ private void clearNode() {// instantiate the headNode headNode = new Node<T>(null, null, null); // Instantiate tailNode and point prev to tailNode = new Node<T>(headNode, null, null); headNode.next = tailNode; Size = 0; }Copy the code

Second, the use of linked list to achieve the operation of data

The list is just the operation of nodes, just a structure, not the real purpose, ultimately to make the list invisible to the outside, just like the human skeleton to the body

Any movement of the body is supported by the skeleton, and the skeleton is not visible, it is just the movement of the body from outside. What we need is to add, delete, modify and check the data according to this structure, and expose the interface to be called by a foreign party

1, the fixed-point add operation –add

@override public void add(int index, T el) {// void add(int index, T el) { if (index < 0 || index > size) { throw new IllegalArgumentException("Add failed. Illegal index"); } addNode(getNode(index), el); }Copy the code

2. Fixed point removal operation –remove

@Override
public T remove(int index) {
    if (index < 0 || index > size) {
        throw new IllegalArgumentException("Remove failed. Illegal index");
    }
    return removeNode(getNode(index));
}
Copy the code

3. Get and Modify –get and set

@Override
public T get(int index) {
    if (index < 0 || index > size) {
        throw new IllegalArgumentException("Get failed. Illegal index");
    }
    return getNode(index).el;
}

@Override
public T set(int index, T el) {
    if (index < 0 || index > size) {
        throw new IllegalArgumentException("ISet failed. Illegal index");
    }
    return setNode(index, el);
}
Copy the code

Iv. Other operations

It’s basically the same as a singly linked list, so I won’t show you.

1. Whether to include an element:

@Override public boolean contains(T el) { Node target = headNode; while (target.next ! = null) { if (el.equals(target.next)) { return true; } } return false; }Copy the code

2. Obtain the matching index based on the specified element

@Override public int[] getIndex(T el) { int[] tempArray = new int[size]; Int index = 0; Int count = 0; Node node = headNode.next; while (node.next ! = null) { if (el.equals(node.el)) { tempArray[index] = -1; count++; } index++; node = node.next; } int[] indexArray = new int[count]; Int indexCount = 0; for (int i = 0; i < tempArray.length; i++) { if (tempArray[i] == -1) { indexArray[indexCount] = i; indexCount++; } } return indexArray; }Copy the code

3. Remove by element :(find, delete…)

@Override public int removeEl(T el) { int[] indexes = getIndex(el); int index = -1; if (indexes.length > 0) { index = indexes[0]; remove(indexes[0]); } return index; } @Override public boolean removeEls(T el) { int[] indexArray = getIndex(el); if (indexArray.length ! = 0) { for (int i = 0; i < indexArray.length; i++) { remove(indexArray[i] - i); -i} return true; } return false; }Copy the code

4. Connect two lists at a fixed point

/////////////// Just implement it. GetHeadNode and getLastNode break the encapsulation of Node, ///////////// @override public IChart<T> contact(IChart<T> IChart) {return contact(0, IChart); } @Override public IChart<T> contact(int index, IChart<T> iChart) { if (! (iChart instanceof LinkedChart)) { return null; } if (index < 0 || index > size) { throw new IllegalArgumentException("Contact failed. Illegal index"); } LinkedChart linked = (LinkedChart) iChart; Node targetNode = getNode(index); Node targetNextNode = targetNode.next; Targetnode.next = linked.getheadNode ().next; targetNode.next = linked.getheadNode ().next; Link.getheadnode ().next. Prev = targetNode; Targetnextnode.prev = linked.getLastNode().prev; targetNextNode.prev = linked.getLastNode().prev; Link.getlastnode ().prev.next = targetNextNode; link.getLastNode ().prev.next = targetNextNode; return this; } public Node getHeadNode() { return headNode; } public Node getLastNode() { return tailNode; } / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / /Copy the code

V. Summary:

1. Pros and cons analysis

Advantages: created dynamically, save a space in the head and tail added easily fixed point insertion/deletion in general is superior to the array list (because most half find array list up all) disadvantages: discrete space, create space fragmentation find relatively difficult, can only from the beginning or end one by one to find better than singly linked lists (but) usage scenarios: The adding and deleting performance of the double linked list is better than that of the array list and the single linked list, and the double linked list is the best when the positions of the double linked list are frequently added and deletedCopy the code

2. Finally put the view together

The interface is the same, the change of the bottom implementation, will not affect the view layer, just the view layer of the monomer drawing change.

The detailed drawing scheme can be found here

/** * @param canvas */ private void dataView(canvas canvas) {mPaint. SetColor (color.blue); mPaint.setStyle(Paint.Style.FILL); mPath.reset(); for (int i = 0; i < mArrayBoxes.size(); i++) { LinkedNode box = mArrayBoxes.get(i); mPaint.setColor(box.color); canvas.drawRoundRect( box.x, box.y, box.x + Cons.BOX_WIDTH, box.y + Cons.BOX_HEIGHT, BOX_RADIUS, BOX_RADIUS, mPaint); mPath.moveTo(box.x, box.y); mPath.rCubicTo(Cons.BOX_WIDTH / 2, Cons.BOX_HEIGHT / 2, Cons.BOX_WIDTH / 2, Cons.BOX_HEIGHT / 2, Cons.BOX_WIDTH, 0); if (i < mArrayBoxes.size() - 1 ) { LinkedNode box_next = mArrayBoxes.get(i + 1); LinkedNode box_now = mArrayBoxes.get(i); If (I % LINE_ITEM_NUM == LINE_ITEM_NUM - 1) {// mPath. RLineTo (0, cons.box_height); mPath.lineTo(box_next.x + Cons.BOX_WIDTH, box_next.y); mPath.rLineTo(Cons.ARROW_DX, -Cons.ARROW_DX); mPath.moveTo(box_next.x, box_next.y); mPath.lineTo(box_now.x, box_now.y+Cons.BOX_HEIGHT); mPath.rLineTo(-Cons.ARROW_DX, Cons.ARROW_DX); } else {mPath. RLineTo (0, cons.box_height / 2.2f); MPath. LineTo (box_next. X +Cons.BOX_WIDTH * 0.2f, box_next. mPath.rLineTo(-Cons.ARROW_DX, -Cons.ARROW_DX); mPath.moveTo(box_next.x, box_next.y); MPath. RLineTo (0, Cons. BOX_HEIGHT / 1.2 f); MPath. LineTo (box_now.x + Cons.BOX_WIDTH * 0.8f, box_now.y + Cons. mPath.rLineTo(Cons.ARROW_DX, Cons.ARROW_DX); } } canvas.drawPath(mPath, mPathPaint); canvas.drawText(box.index + "", box.x + Cons.BOX_WIDTH / 2, box.y + 3 * OFFSET_OF_TXT_Y, mTxtPaint); canvas.drawText(box.data + "", box.x + Cons.BOX_WIDTH / 2, box.y + Cons.BOX_HEIGHT / 2 + 3 * OFFSET_OF_TXT_Y, mTxtPaint); }}Copy the code

Further updates in this series link collection :(dynamic updates)

Visible data structures: the introduction to the Android version
Array Tables for Android (Data Structures)
Android Array Table (View Section)
Visible data structure Android version of the single linked list
Visible data structure Android version of the double Linked list
Visible data structure stack for Android version
Visible data structure of the Android version of the queue article
Visible data structure Android version of the binary search tree
More data structures – more on that later

Postscript: Jie wen standard

2. Growth records and errata of this paper

Program source code	The date of	note
V0.1 – making	2018-11-23	Visible data structure – Android version of the dual-linked list implementation

3. More about me

Pen name	QQ	WeChat	hobby
Zhang Feng Jie te Li	1981462002	zdl1994328	language
My lot	My Jane books	I’m the nuggets	Personal website

4. A statement

1—- This article is originally written by Zhang Fengjie, please note if reproduced

2—- welcome the majority of programming enthusiasts to communicate with each other 3—- personal ability is limited, if there is something wrong welcome to criticize and testify, must be humble to correct 4—- see here, I thank you here for your love and support