线性表的链式存储结构

说到链表，我们先来说一说链表和我们之前所学数组得区别有哪些？

数组存储数据是将元素在内存中连续存放，并且每个内存单元大小也是一致的，查询时是通过数组下标进行查找
链表是与数组相反，存放的顺序是不连续的，并且是通过指针将存储的元素联系到一起的

另外我们也了解到链表的增删操作相较于数组是比较快的，恰恰相反数组的查改操作比较快。

接下来我们引用官方的定义来对链表做一个简单的了解：

链表是一种物理存储单元上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。链表由一系列结点（链表中每一个元素称为结点）组成，结点可以在运行时动态生成。每个结点包括两个部分：一个是存储数据元素的数据域，另一个是存储下一个结点地址的指针域。相比于线性表顺序结构，操作复杂。由于不必须按顺序存储，链表在插入的时候可以达到O(1)的复杂度，比另一种线性表顺序表快得多，但是查找一个节点或者访问特定编号的节点则需要O(n)的时间，而线性表和顺序表相应的时间复杂度分别是O(logn)和O(1)。

由官方定义我们可以得到以下几点：

链表是非连续、非顺序的一种存储结构；
链表由一系列的结点构成，结点是由数据域和指针域域构成；

接下来我们先来了解几个相关概念（定义）

头节点：顾名思义就是第一个结点（所谓‘头’也就是第一个结点），结点我们有真实头结点（第一个结点存储数据）和虚拟头结点（第一个结点不存储数据）之分，在我们的课程中采用的都是虚拟头结点。

由图可以看到，第一个结点（头结点）存储的数据是a1，所以这是一个真实的头结点，如果链表为空，就没有结点。

由上图可以看到头结点是一个虚拟结点，它所指向的下一个结点才是这个链表存储的第一个数据，当然如果链表为空，则会有一个结点，也就是虚拟的结点。

头指针（head）：它是一个引用变量，用来存储头结点的地址的一个指针
尾指针（rear）:和头指针一样，但是是指向链表的最后一个结点的指针

注意：当链表为空，头指针和尾指针均指向头结点（虚拟节点）

链表的实现

关于链表的实现是通过实现之前我们在线性表中所写的接口(List)

public class LinkedList<E> implements List<E> {

}

首先节点（Node）应该为LinkedList（链表）中的一个内部类，那么什么是内部类？内部类就是在内里面定义一个类，其权限是私有的（private），因为不需要在外部去创建对象。

private class Node{
    	 E data;//数据域
    	 Node next;//指针域
         /**
          *Node的没有参数的构造函数
          */

    	 public Node() {
    		/* data=null;
    		 next=null;*/
    		 this(null,null);
    	 }
          /**
          *Node的带有参数的构造函数
          */
    	 public Node(E data,Node next) {
    		 this.data=data;
    		 this.next=next;
    	 }
         //重新toString方法，用于创建对象时将其打印出来
    	 @Override
    	public String toString() {
    		// TODO Auto-generated method stub
    		return data.toString();
    	}
     }

关于接口List的实现，具体方法如下：

需要定义的变量有头指针和尾指针，另外还需要一个变量来判断纪录元素的个数。

     private Node head;//指向头结点得头指针
     private Node rear;//指向尾结点得尾指针
     private int size;//纪录元素得个数

LinkedList的构造函数，有参数和无参数的构造函数

因为时虚拟节点，所以先创建一个新的节点，head指向新的结点；
尾指针和头指针指向的是同一个结点，所以rear=head；
链表为空，size=0。

     public LinkedList() {
    	 head=new Node();
    	 rear=head;
    	 size=0;
     }
     public LinkedList(E[] arr) {
    	/* head=new Node();
    	 rear=head;
    	 size=0;*/
    	 this();
    	 for(E e:arr) {
    		 addLast(e);
    	 }

getSize()方法用于获取线性表中的有效元素个数，这里就直接返回size就可以

    @Override
	public int getSize() {
		// TODO Auto-generated method stub
		return size;
	}

isEmpty()方法是用来判别线性表是否为空，链表为空的条件有：

有效元素个数为0，size==0;
头结点的next(我们称之为‘下一跳’）为空，head.next==null

   @Override
	public boolean isEmpty() {
		// TODO Auto-generated method stub
		return size==0&&head.next==null;
	}

add () ——插入方法，插入分为头插入、尾插入和头插和一般插入三种方式，具体实现思路如下：

头插入（每次插入的结点都在第一个结点）——头插入又分为两种情况：

情况一：链表为空（头指针尾指针都指向头结点）的时候插入一个新的结点（先将元素A封装为新的结点）其中结点的数据域为A元素，指针域为Null，首先我们将头结点的下一跳赋给新结点的下一跳，然后再把新元素的地址给头结点的下一跳，注意尾指针要指向新结点（要移动尾指针）

要移动尾指针（空指针插入第一个元素）

情况二：在链表有结点（有数据或者有元素）的时候进行头插入，首先我们将头结点的下一跳赋给新结点的下一跳，然后再把新元素的地址给头结点的下一跳，尾指针不需要移动

2.尾插入——尾插人也分为两种情况：

情况一：链表为空的时候进行尾插入，其原理和头插入是的情况一完全相同
情况二：当链表有数据也就是元素的时候进行尾插人，首先将新元素封装为一个新的结点，然后将新结点的地址赋给尾元素的下一跳，最后尾指针后移至新结点

3.头插和尾插相结合——这种插入方式就是把第一种头插法和第二种尾插法相结合起来，根据实际插入的情况，选择合适的插入方法

4.一般插入——一般插入是指不在头和尾插入，在链表中间插入，或者其他地方（除头和尾），例如下面这个例子要在A和B之间插入D，我们要先找到A结点，然后把A的下一跳给D，然后把D的地址给A的下一跳。

public void add(int index, E e) {
		// TODO Auto-generated method stub
		if(index<0||index>size) {
			throw new IllegalArgumentException("插入角标非法");
		}
		Node n=new Node();
		n.data=e;
		n.next=null;
		if(index==0) {  //头插入
			/*Node n=new Node();
			n.data=e;
			n.next=null;*/
			n.next=head.next;
			head.next=n;
			if(size==0) {
				rear=n;
			}
//			size++;
			/*if(size==1) {
				rear=n;
			}*/
			
		}else if(index==size){  //尾插人
			/*Node n=new Node();
			n.data=e;
			n.next=null;
			rear.next=n;*/
//			rear.next=new Node(e,null);
			rear.next=n;
			rear=rear.next;
//			size++;
		}else {  //其他插入
			Node p=head;
			for(int i=0;i<index;i++) {
				p=p.next;
			}
			n.next=p.next;
			p.next=n;
//			size++;
		}
		size++;
	}

addFirt（）和 addLast（）——在表头插入新元素和在表尾插入新元素，在表头插入元素是在角标0处，在表尾插入元素是在角标size处

@Override
	public void addFirst(E e) {
		// TODO Auto-generated method stub
		add(0,e);
		}

	@Override
	public void addLast(E e) {
		// TODO Auto-generated method stub
		add(size,e);
	}

get（）——获取链表中的元素，分为指定元素、表头元素和表尾元素，在获取指定元素的时候分为三种（表头、表尾和其他），每种情况的代码实现如下：

@Override
	public E get(int index) {
		// TODO Auto-generated method stub
		if(index<0||index>size) {
			throw new IllegalArgumentException("查找角标非法");
		}
		if(index==0) {
			return head.next .data;
		}else if(index==size-1) {
			return rear.data;
		}else {
			Node p=head;
			for(int i=0;i<=index;i++) {
				p=p.next;
			}
			return p.data;
		}
		
	}
   //查找头元素，直接为get(0)
	@Override
	public E getFirst() {
		// TODO Auto-generated method stub
		return get(0);
	}

	@Override
	public E getLast() {
		// TODO Auto-generated method stub
		return get(size-1);
	}

set（）——修改角标，在线性表中其方法定义修改线性表中指定index处的元素为所有新元素，在链表中同样也是这样的，在这个方法中同样分为三种情况（头，尾和其他），思路是和上面的get()方法是非常雷同的，具体代码实现如下：

@Override
	public void set(int index, E e) {
		// TODO Auto-generated method stub

		if (index < 0 || index > size) {
			throw new IllegalArgumentException("修改角标非法");
		}
		if(index==0) {
			 head.next .data=e;
		}else if(index==size-1) {
			rear.data=e;
		}else {
			Node p=head;
			for(int i=0;i<=index;i++) {
				p=p.next;
			}
			p.data=e;
		}
		
	}

contains()和find()——这两个方法都是查找的方法，其中contains()方法的实现是建立在find()方法基础之前，我们先来说一说这两个方法的含义都是什么，contains() 判表中是否包含指定元素e 默认从前往后找，find()在表中获取指定元素e的角标默认是从前往后找，关于find()方法的实现主要分为几个步骤：首先判断链表是否为空，如果为空，则返回-1；如果不为空，我们要遍历链表中的元素（循环），最后返回角标。因此contains()方法的实现只要满足find()方法中的不返回-1即可，通俗讲就是只要不为空，肯定能找到指定的元素。

public boolean contains(E e) {
		// TODO Auto-generated method stub
		return find(e)!=-1;
	}

	@Override
	public int find(E e) {
		// TODO Auto-generated method stub
		int index=-1;
		if(isEmpty()) {
			return index;
		}
		Node p=head;
		while(p.next!=null){
			p=p.next;
			index++;
			if(p.data==e) {
				return index;
				
			}
		}
		
		return -1;
	}

remove() ——删除的方法与插入一样也分为头删、尾删和一般删，具体实现思路如下：

头删：头删顾名思义删除第一个结点，把要删除的结点的下一跳给头（head）的下一跳即可，但是现在所删除的结点依然指向它的下一个结点，所以我们需要把它的next情况，也就是为null,当然也可以不清，因为Java中有垃圾回收机制。如下图我们要删除A，我们需要把A的下一跳给head的下一跳，然后A的下一跳赋值为null:

但是有个特殊情况就是要删除结点的时候，链表中只要一个结点（数据），这时候我们要把头结点的下一跳为null（这个时候要删除的结点的下一跳为null,把要删除的结点的下一跳给头结点的下一跳）,尾指针需要移动到头结点

2.尾删：尾删就是删除链表的尾结点，我们需要先找到尾结点的上一个节点，然后把其下一跳赋为null,然后尾指针移到其位置上，（或者先移动尾指针，然后再将下一跳赋null）这里没有特殊情况，因为删除尾结点，尾指针一直在移动

3.一般删除：一般删除就是除了删除头结点和尾结点，删除链表中的其他结点，如下图，要删除结点B，我们要先找到A结点（要删除结点的上一个节点），然后将B的下一跳赋给A的下一跳

@Override
	public E remove(int index) {
		// TODO Auto-generated method stub
		if(index<0||index>=size) {
			throw new IllegalArgumentException("删除角标非法");
		}
		E res=null;
		if(index==0) {
			Node p=head.next;
			res=p.data;
			head.next=p.next;
			p.next=null;
			p=null;
			if(size==1) {
			  rear=head;
			}
			
		}else if(index==size-1) {
			Node p=head;
			 res=rear.data;
			while(p.next!=rear){
				p=p.next;
				
			}
			p.next=null;
			rear=p;
			
		}else {
			Node p=head;
			for(int i=0;i<index;i++) {
				p=p.next;
			}
			/*E res=p.next.data;
			p.next=p.next.next;*/
		
			Node del=p.next;
			res=del.data;
			p.next=del.next;
			del.next=null;
			rear=p;
			
			
					
		}
		size--;
		return res;
	
	}

	@Override
	public E removeFirst() {
		// TODO Auto-generated method stub
		return remove(0);
	}

	@Override
	public E removeLast() {
		// TODO Auto-generated method stub
		return remove(size-1);
	}

removeElement（）——删除表中的指定元素，通过调用上面的删除方法，给定角标即可完成删除操作

@Override
	public void removeElement(E e) {
		// TODO Auto-generated method stub
		int index=find(e);
		if(index<0||index>=size) {
			throw new IllegalArgumentException("删除角标非法");
		}
		remove(index);
	}

clear（）——清空操作，相当于将头结点的下一跳为null，尾指针指向头结点，同时size=0

@Override
	public void clear() {
		// TODO Auto-generated method stub
		head.next=null;
		rear=head;
		size=0;
	}

toString()的重写——先创建一个字符流StringBuilder对象，然后需要先判定链表是否为空，如果为空直接打印“[]”，如果不为空需要拼接字符串，先打印“[”，然后将元素遍历出来，想要将元素打印出来，在遍历过程中我们还要做一个判断就是是否是最后一个元素，如果是打印“]”，如果不是打印“，”。

    @Override
	public String toString() {
		// TODO Auto-generated method stub
		StringBuilder sb=new StringBuilder();
		sb.append("LinkedList:size="+getSize()+"\n");
		if(isEmpty()) {
			sb.append("[]");
		}else {
			sb.append('[');
			Node p=head;
			while(p.next!=null){
				p=p.next;
				if(p==rear) {
					sb.append(p.data+"]");
				}else {
					sb.append(p.data+",");
				}
			}
		}
		return sb.toString();
	}

equals()——equals方法是和我们之前所讲的线性表的equals方法一样，所以完全可以拿过来用

@Override
	public boolean equals(Object obj) {
		// TODO Auto-generated method stub
		if(obj==null) {
			return false;
		}
		if(obj==this) {
			return true;
		}
		if(obj instanceof LinkedList) {
			LinkedList l=(LinkedList) obj;
			   if(getSize()==l.getSize()) {
				   for(int i=0;i<getSize();i++) {
					   if(get(i)!=l.get(i)) {
						   return false;
					   }
				   }
				   return true;
			   }
		   }
		return false;
	}

测试类的编写

public static void main(String[] args) {
		// TODO Auto-generated method stub
       LinkedList<Integer> list=new LinkedList<Integer>();
       for(int i=1;i<=10;i++) {
    	   list.addFirst(i);
       }
       System.out.println(list);
       for(int i=11;i<=15;i++) {
    	   list.addLast(i);
       }
       System.out.println(list);
       System.out.println(list.getFirst());
       System.out.println(list.getLast());
       for(int i=1;i<=5;i++) {
    	   list.removeFirst();
    	   list.removeLast();
       }
      System.out.println(list);
       list.removeFirst();
       list.removeFirst();
       list.removeFirst();
       list.removeFirst();
       list.removeFirst();
       System.out.println(list);
       for(int i=1;i<=10;i++) {
    	   list.addFirst(i);
       }
       System.out.println(list);
       System.out.println(list.getFirst());
       System.out.println(list.getLast());
}

运行结果：

原文链接：https://blog.csdn.net/qq_44941119/article/details/100834092