一、单链表的实现
无头单向非循环链表
定义异常用于判断所给位置是否合法
public class IndexNotLegal extends RuntimeException{
public IndexNotLegal(){
}
public IndexNotLegal(String smg){
super(smg);
}
}class ListNode中包含当前节点的值和下一个节点指向
实现链表的头插，尾插，任意位置插入，查找，删除一个节点，打印，计数，清空
import java.util.List;
public class MySingleList {
//节点
class ListNode{
public int val;
public ListNode next;
public ListNode(int val){
this.val = val;
next = null;
}
}
public ListNode head;//代表链表的头结点
//打印
public void display(){
ListNode cur = head;
while(cur!=null){
System.out.print(cur.val+"->");
cur = cur.next;
}
System.out.println();
}
//节点个数
public int size(){
int count = 0;
ListNode cur = head;
while(cur!=null){
count++;
cur = cur.next;
}
return count;
}
//头插
public void addFirst(int data){
ListNode node = new ListNode(data);
node.next = head;
head = node;
}
//尾插法
public void addLast(int data){
ListNode node = new ListNode(data);
if(head==null){
head = node;
return;
}
ListNode tail = head;
while(tail.next != null){
tail=tail.next;
}
tail.next = node;
}
//任意位置插入,第一个数据节点为0号下标
public void addIndex(int index,int data){
//判断合不合法
try {
checkIndex(index);
}catch(IndexNotLegal e){
e.printStackTrace();
}
if(index==0){
addFirst(data);
return;
}
if(index == size()){
addLast(data);
return;
}
ListNode cur = findIndexSubOne(index);
ListNode node = new ListNode(data);
node.next = cur.next;
cur.next = node;
}
private void checkIndex(int index) throws IndexNotLegal{
if(index<0||index>size()){
throw new IndexNotLegal("index不合法");
}
}
public ListNode findIndexSubOne(int index){
ListNode cur = head;
int count =0;
while(count!=index-1){
cur = cur.next;
count++;
}
return cur;
}
//查找是否包含关键字key是否在单链表当中
public boolean contains(int key){
ListNode cur = head;
while(cur!=null){
if(cur.val==key){
return true;
}
cur = cur.next;
}
return false;
}
//删除出现关键字为key的节点
public void remove(int key){
if(head==null){
return;
}
ListNode del = head;
ListNode pre = head;
while(del!=null){
if(del.val==key){
pre.next = del.next;
del = del.next;
}else{
pre = del;
del = del.next;
}
}
if(head.val==key){
head = head.next;
return;
}//最后判断头结点
}
public void clear(){
ListNode cur = head;
while(cur!=null){
ListNode curN = cur.next;
cur.next = null;
cur = curN;
}
head = null;
}
}
二、LinkedList
1、介绍
LinkedList的底层是双向链表结构，由于链表没有将元素存储在连续的空间中，元素存储在单独的节点中，然后通过引用将节点连接起来了，因此在任意位置插入或者删除元素时，不需要搬移元素，效率比较高。
LinkedList实现了List接口
LinkedList的底层使用了双向链表
LinkedList没有实现RandomAccess接口，因此LinkedList不支持随机访问
LinkedList的任意位置插入和删除元素时效率比较高，时间复杂度为O(1)
LinkedList比较适合任意位置插入的场景
2、方法介绍
add
直接增加
插入到指定位置
addAll：尾插c 中的所有元素
remove
删除 index 位置元素
删除遇到的第一个 o
get：获取下标 index 位置元素
set：将下标 index 位置元素设置为 element
clear：清空
contains：判断 o 是否在线性表中
indexOf：返回第一个 o 所在下标
lastIndexOf：返回最后一个 o 的下标
subList：截取部分 list
三、LinkedList遍历方法
public static void main1(String[] args) {
LinkedList<Integer> list = new LinkedList<>();
list.add(1);
list.add(2);
list.add(1,3);
System.out.println(list);//直接打印
System.out.println("==============");
//foreach遍历
for(Integer x: list){
System.out.print(x+" ");
}
System.out.println();
System.out.println("============");
//for遍历
int size = list.size();
for (int i = 0; i < size; i++) {
System.out.print(list.get(i)+" ");
}
System.out.println();
System.out.println("============");
//使用迭代器遍历-正向遍历
Iterator<Integer> it = list.iterator();
while(it.hasNext()){
System.out.print(it.next()+" ");
}
System.out.println();
System.out.println("============");
Iterator<Integer> it2 = list.listIterator();
while(it2.hasNext()){
System.out.print(it2.next()+" ");
}
System.out.println();
System.out.println("============");
//使用迭代器遍历-反向遍历
ListIterator<Integer> it3 = list.listIterator(list.size());
while(it3.hasPrevious()){
System.out.print(it3.previous()+" ");
}
System.out.println();
System.out.println("============");
}
四、实现MyLikedList
无头双向链表
定义异常用于判断所给位置是否合法
public class IndexNotIllegal extends RuntimeException{
public IndexNotIllegal(){
}
public IndexNotIllegal(String smg){
super(smg);
}
}方法实现
public class MyLinkedList {
static class ListNode{
public int val;
public ListNode prev;
public ListNode next;
public ListNode(int val){
this.val = val;
}
}
public ListNode head;//头结点
public ListNode last;//尾节点
public int size(){
int size = 0;
ListNode cur = head;
while(cur!=null){
size++;
cur = cur.next;
}
return size;
}
public void display(){
ListNode cur = head;
while(cur!=null){
System.out.print(cur.val+" ");
cur = cur.next;
}
System.out.println();
}
public boolean contains(int key){
ListNode cur = head;
while(cur!=null){
if(cur.val==key){
return true;
}
cur = cur.next;
}
return false;
}
//头插法
public void addFirst(int data){
ListNode Node = new ListNode(data);
if(head==null){
head = last = Node;
}else{
Node.next = head;
head.prev = Node;
head = Node;
}
}
//尾插法
public void addLast(int data){
ListNode Node = new ListNode(data);
if(head==null){
head = last = Node;
}else{
last.next = Node;
Node.prev = last;
last = Node;
}
}
//任意位置插入,第一个数据节点为0号下标
public void addIndex(int index,int data){
try{
checkIndex(index);
}catch(RuntimeException e){
e.printStackTrace();
}
if(index == 0){
addFirst(data);
return;
}
if(index == size()){
addLast(data);
return;
}
ListNode cur = findIndex(index);
ListNode node = new ListNode(data);
node.prev = cur.prev;
node.next = cur;
cur.prev.next = node;
cur.prev = node;
}
private ListNode findIndex(int index){
ListNode cur = head;
while(index!=0){
cur = cur.next;
index--;
}
return cur;
}
public void checkIndex(int index)throws IndexNotIllegal{
if(index<0||index>size()){
throw new IndexNotIllegal("数组下标不合法");
}
}
//删除第一次出现关键字为key的节点
public void remove(int key){
ListNode cur = head;
while(cur!=null){
if(cur.val==key) {
if (cur == head) {
//处理头节点
head = head.next;
if(head != null){
head.prev = null;
}else{
last = null;
}
} else {
if (cur.next == null) {
//处理尾节点
cur.prev.next = cur.next;
last = last.prev;
} else {
cur.prev.next = cur.next;
cur.next.prev = cur.prev;
}
}
return;//删完一个就跳出
}
cur = cur.next;
}
}
//删除所有值为key的节点
public void removeAllKey(int key){
ListNode cur = head;
while(cur!=null){
if(cur.val==key) {
if (cur == head) {
//处理头节点
head = head.next;
if(head != null){
head.prev = null;
}else{
last = null;
}
} else {
if (cur.next == null) {
//处理尾节点
cur.prev.next = cur.next;
last = last.prev;
} else {
cur.prev.next = cur.next;
cur.next.prev = cur.prev;
}
}
}
cur = cur.next;
}
}
//得到单链表的长度
public void clear(){
ListNode cur = head;
while(cur!=null){
ListNode curN = cur.next;
cur.next = null;
cur.prev = null;
cur = curN;
}
head = last = null;
}
}