1.链表的图示

节点 

class ListNode{//结点public int val;public ListNode next;public ListNode(int val) {this.val = val;}}public ListNode head;//永远指向我的头节点，头节点是链表属性不是节点属性

 2.学会建立一个链表

//首先学习创建一个链表
//1.建立五个节点，此时这五个节点毫无关系
//2.建立关系

public void createList(){ListNode node1=new ListNode(12);ListNode node2=new ListNode(7);ListNode node3=new ListNode(8);ListNode node4=new ListNode(9);ListNode node5=new ListNode(10);node1.next=node2;node2.next=node3;node3.next=node4;node4.next=node5;//头节点this.head=node1;

3.链表的实现

public class SeqList {private int[] array;private int size;// 默认构造方法SeqList(){ }// 将顺序表的底层容量设置为initcapacitySeqList(int initcapacity){ }// 新增元素,默认在数组最后新增public void add(int data) { }// 在 pos 位置新增元素public void add(int pos, int data) { }// 判定是否包含某个元素public boolean contains(int toFind) { return true; }// 查找某个元素对应的位置public int indexOf(int toFind) { return -1; }// 获取 pos 位置的元素public int get(int pos) { return -1; }// 给 pos 位置的元素设为 valuepublic void set(int pos, int value) { }//删除第一次出现的关键字keypublic void remove(int toRemove) { }// 获取顺序表长度public int size() { return 0; }// 清空顺序表public void clear() { }// 打印顺序表，注意：该方法并不是顺序表中的方法，为了方便看测试结果给出的public void display() { }
}

3.1 show的实现

打印链表的实现

public void show(){ListNode cur=head;while(cur!=null){//注意条件System.out.print(cur.val+" ");cur=cur.next;}System.out.println();}

 //此处的cur相当于一个替身

//定义一个新的引用节点需要new，不能让head为空，故需要找一个替身

3.2 contains的实现

//查找是否包含关键字key是否在单链表中

public boolean contains(int key){ListNode cur=head;while(cur!=null){if(cur.val==key)return true;cur=cur.next;}return false;}

检测

        System.out.println(mySingleList.contains(12));System.out.println(mySingleList.contains(10));System.out.println(mySingleList.contains(66));

//如果val值是引用类型，则不能用==来比较，只能用equals来比较

3.3 size的实现

//得到单链表的长度 --> 链表中节点的个数 

public int size(){int count=0;ListNode cur=head;while(cur!=null){cur=cur.next;count++;}return count;}

3.4 addFirst的实现

//头插法

//实行此等操作，应当先后后前

public void addFirst(int data){ListNode node=new ListNode(data);node.next=head;head=node;}

3.5 addLast的实现

//尾插法

public void addLast(int data){ListNode node=new ListNode(data);if(head == null) {head = node;return;}//原先是空的，直接就可以使得头节点为nodeListNode cur = head;while (cur.next != null) {cur = cur.next;}//cur指向的节点就是尾巴节点cur.next = node;}

检测

mySingleList.addLast(22);
mySingleList.show();

 3.6 addIndex的实现

//在index前进行插入

public void addIndex(int index,int data){int len = size();//1.首先需要判断位置合法if(index < 0 || index > len) {throw new IndexOutOfBounds("任意位置插入数据的时候，index位置不合法: "+index);}if(index==len){addLast(data);return;}if(index==0){addFirst(data);return;}else{//1.先找到index-1的位置ListNode cur=findIndex(index);//2.进行插入ListNode node=new ListNode(data);node.next=cur.next;cur.next=node;}}

//找到的是前一个index 

private ListNode findIndex(int index){ListNode cur =head;while(index-1!=0){cur=cur.next;index--;}return cur;}

检测 

        mySingleList.addIndex(0,1);mySingleList.show();mySingleList.addIndex(2,10);mySingleList.show();mySingleList.addIndex(9,100);mySingleList.show();

3.7 remove的实现

//删除节点

public void remove(int key){if(head == null) {return;}if(head.val == key) {head = head.next;return;}ListNode prev = searchPrev(key);if(prev == null) {System.out.println("没有这个数据！");return;}ListNode del = prev.next;prev.next = del.next;}

private ListNode searchPrev(int key) {ListNode prev = head;while (prev.next != null) {if(prev.next.val == key) {return prev;}else {prev = prev.next;}}return null;}

检测

        mySingleList.remove(1);mySingleList.show();mySingleList.remove(100);mySingleList.show();mySingleList.remove(12);mySingleList.show();

3.8 clear的实现

//使每一个节点都被回收

  public void clear() {//this.head = null;while (head != null) {ListNode headNext = head.next;head.next = null;head = headNext;}}