java知识4-----数据结构 List

java知识4-----数据结构 List

这里写目录标题

数据结构概念

逻辑结构：物理结构经典数据结构

线性表（List）：

顺序存储方式线性表（ArrayList）：链式存储方式线性表（linkedList）：

链表的插入：链表的删除： 循环链表双向循环链表

双向循环链表的插入双向循环链表的删除 ArrayListlinkedList继承结构

数据结构概念

数据结构：数据之间相互存在着一种或多种特定的关系的元素的集合。

逻辑结构：

数据对象中数据元素之间的相互关系分为：

集合结构线性结构属性结构图形结构

物理结构

物理结构即存储结构。

顺序存储结构链式存储结构

经典数据结构 线性表（List）： 顺序存储方式线性表（ArrayList）：

存储位置连续，可以方便计算各个元素的地址。
优点：查询块；
缺点：插入和删除慢；

链式存储方式线性表（linkedList）：

线性表的链式存储结构的特点是，用一组任意的存储单元存储线性表的数据元素，这组存储单元可以是连续的，也可以是不连续的。
优点：删除和插入快；
缺点：查询慢；

链表的插入：

在p节点和p的next节点中间插入s节点：
s->next = p->next ;
p->next = s ;

链表的删除：

将p节点和p的next的next节点中间的p的next节点删除：
p->next = p->next->next ;

循环链表

将单链表中终端结点的指针端由空指针改为指向头结点，就使整个单链表形成一个环，这种头尾相连的单链表称为单循环链表，简称循环链表。

双向循环链表

双向循环链表是单向循环链表的每个结点中，再设置一个指向其前驱结点的指针域。

双向循环链表的插入

P节点和p的next节点中间插入s节点：
s->prior = p; // 把p赋值给s的前驱
s->next = p->next; //把p->next 赋值给s的后继
p->next->prior = s; //把s赋值给p->next的前驱
p->next = s; // 把s赋值给p的后继

双向循环链表的删除

p的前驱，p节点，p的后继中，删除p节点：
p->prior->next = p->next; //把p-next 赋值给 p-prior 的后继
p->next->prior = p->prior; //把p-prior 赋值给p->next 的前驱

ArrayList

ArrayList内部使用的了一个Object数组来存储数据元素，所以ArrayList开辟的是一块连续的内存，是顺序存储的，有所有顺序存储的特性，查询快，插入删除慢。

linkedList

linkedList是链式存储的，具有链式存储的所有特性，查询慢，插入删除快。

继承结构

ArrayList

public class ArrayList extends AbstractList
        implements List, RandomAccess, Cloneable, java.io.Serializable {}
        
	public abstract class AbstractList extends java.util.AbstractCollection 
			implements java.util.List {}
	
		public abstract class AbstractCollection implements Collection {}
			public interface Collection extends java.lang.Iterable {}
			public interface Iterable {}
		public interface List extends Collection {}
			public interface Collection extends java.lang.Iterable {}
			public interface Iterable {}
	
	public interface List extends Collection {}	
	public interface RandomAccess {}
	public interface Cloneable {}
	public interface Serializable {}

linkedList

public class linkedList
    extends AbstractSequentialList
    implements List, Deque, Cloneable, java.io.Serializable {}

	public abstract class AbstractSequentialList extends java.util.AbstractList {}

		public abstract class AbstractList extends java.util.AbstractCollection 
				implements java.util.List {}
		
			public abstract class AbstractCollection implements Collection {}
				public interface Collection extends java.lang.Iterable {}
				public interface Iterable {}
			public interface List extends Collection {}
				public interface Collection extends java.lang.Iterable {}
				public interface Iterable {}
				
	public interface List extends Collection {}	
	public interface Deque{}
		public interface Deque extends java.util.Queue {}
			public interface Queue extends Collection {}
				public interface Collection extends java.lang.Iterable {}
				public interface Iterable {}
	public interface Cloneable {}
	public interface Serializable {}

总结：
从继承结构看，ArrayList和linkedList是基本一致的，毕竟他们都是List，区别就在他们的特性上，ArrayList特性是使用连续内存存储，内部是一个数组。
linkedList可以认为是在ArrayList的基础上进行了改良，在非整块内存使用上体现优势，它是链式存储，内存可以是连续的，也可以是不连续的，大大提升了内存使用率，当然linkedList在这种情况下是最优的。
linkedList和ArrayList对比，它的特性
首先，是通过实现Deque这个队列，
其次：
1，是在ArrayList与父类AbstractList之间增加了AbstractSequentialList来增加其独有特性。
2，是增加AbstractCollection这一条父类，实现了直接挂钩到了List的父类Collection；同时也像ArrayList一样保留了List的这一条继承路线。

总结来说，linkedList是ArrayList的增强改良版本，在特性情况下可以有比ArrayList更优良的表现，但是在一些情况下ArrayList也是比linkedList表现更优秀，具体使用哪个线性表，需要根据实际情况来定。

调整一下图结构，以便显示的整齐一些，但是整齐了并不如上图杂乱的时候看的更一目了然。