1.简介
链表是一种物理存储单元上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。 链表由一系列结点（链表中每一个元素称为结点）组成，结点可以在运行时动态生成。 每个结点包括两个部分：一个是存储数据元素的数据域，另一个是存储下一个结点地址的指针域——出自百度百科
链表存储在“节点”（Node）中
public class Node{
private E e;
private Node next;
}
image.png
这里的1，2，3是数据也就是e，指向下一个的箭头是next。
优点：不会受固定容量的限制
缺点：丧失了随机访问的能力
2.链表的实现
首先创建一个类，命名为LinkedList，其中包含一个私有的内部类Node，设置为私有的原因是因为不想让外部知到链表的具体实现细节。内部类Node中又有两个共有的属性E类型的e和Node类型的next，设置为共有的原因是因为这样可以让外部类直接进行操作。然后再相应的生成构造方法。
public class LinkedList<E> {
private class Node{
public E e;
public Node next;
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();
}
}
}
当用户传入两个参数，此时会调用第一个构造方法。如果只传入了元素e，那么就直接复用上面的构造方法，next直接传入null就好了。如果什么参数都不传入就都为null。
为Node类设置完参数和构造方法之后我们再为LinkedList类添加参数和构造方法。
private Node dummyHead;
private int size;
public LinkedList(){
dummyHead = new Node(null,null);
size = 0;
}
首先为了方便在链表中添加元素，我设置一个虚拟头节点dummyHead，因为添加元素首先要找到待添加位置的前一个，所以就设置了这个虚拟头节点，它位于索引0之前的位置。然后添加size属性方便链表的一些操作。添加完属性之后再编写一个构造方法，在构造方法中首先将虚拟头节点的值设置为null，next指针也设置为null，将size初始化为0。
- getSize()、isEmpty()方法
public int getSize(){
return size;
}
public boolean isEmpty(){
return size == 0;
}
做完了准备工作，我们首先来实现两个简单的方法，第一个方法直接返回size就可以知到size的值了。第二个当size为0时便是空的返回true，否则为false。
- add相关方法
在索引为1的位置添加元素666的详细过程如下：
image.png
image.png
image.png
image.png
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;
}
Node node = new Node(e);
node.next = prev.next;
prev.next = node;
// prev.next = new Node(e,prev.next);
size++;
}
public void addFirst(E e){
add(0,e);
}
public void addLast(E e){
add(size,e);
}
编写add方法需要两个参数，一个是需要添加的位置index（实际上链表中是没有索引这个概念的，这里声明索引只不过是为了让添加更加形象）和待添加的元素e。因为需要用户传入index，所以就需要判断index的合法性。如果不合法则抛出异常否则进行添加。接着声明出一个叫previous的节点（这里简写为prev）它代表着待添加位置的上一个位置，将它设置为前面声明的dummyHead。然后进行循环，循环到index-1的位置时正好是待添加位置的前一个，在循环中只需要将prev向后移动。到达了位置时首先需要创建一个节点node其中包含元素e，然后将node的next指针指向prev的下一个位置。然后将prev.next指向node，然后不要忘记对size的维护，这样add方法就完成了。既然完成了add那么向链表头和链表末尾添加元素只需要复用即可。
- get()相关方法
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);
}
get()方法首先需要传入一个index，既然需要传入index那就一定离不开判断index的合法性了。如果合法程序就继续执行，首先创建一个Node类型的current（简写为cur），cur为第一个元素。然后进行for循环的遍历，遍历到index，期间一直将cur向后移动。循环完成后直接返回cur中存放的元素e。剩下的getFirst()和getLast()方法就直接复用get()即可。
- set()方法
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;
}
set方法需要将想要修改的位置和元素传入，然后进行索引合法性判断。如果下标合法之后创建一个Node类型的cur，将它设置为从第一个元素开始。然后进行循环到index，期间cur一直向后移动。循环完成后将cur中的元素值设置为传入的元素值即可。
- contains()方法
public boolean contains(E e){
Node cur = dummyHead.next;
for (int i = 0; i < size; i++) {
if (cur.e.equals(e)){
return true;
}
cur = cur.next;
}
return false;
}
contains()方法用来判断链表中是否包含元素e，所以需要传入E类型的e，然后创建Node类型的元素cur，cur从第一个元素开始。然后进行循环，次数为链表中当前元素数，在这期间如果有元素与传入的e相同则return true，否则继续将cur向后移动。直至循环结束也没有相同的元素的话就返回false。
- remove()方法
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 delNode = prev.next;
prev.next = delNode.next;
delNode.next = null;
size--;
return delNode.e;
}
public E removeFirst(){
return remove(0);
}
public E removeLast(){
return remove(size-1);
}
remove()方法首先需要传入int类型的index，传入之后进行索引的合法性判断，如果是合法的就创建一个Node类型的prev，将它设置为第一个元素的位置，然后进行for循环进行index-1次，期间一直将prev向后移动。移动完成后创建Node类型的delNode保存待删除的元素。然后将元素进行删除，对size进行维护并将结果返回。完成之后便可以复用remove()方法对链表头和链表末尾进行元素的删除了。
- toString()方法
@Override
public String toString(){
StringBuilder res = new StringBuilder();
Node cur = dummyHead.next;
while (cur != null){
res.append(cur + "-->");
cur = cur.next;
}
res.append("NULL");
return res.toString();
}
为了测试方便，对toString方法进行的重写。
网友评论