单链表
链表应该是IT领域比较重要的一种数据结构了，几乎可以在各个操作系统，各种编程语言，各个软件中都可见到。
比如Mysql的三种链表用于进行数据页分配，脏页处理以及缓存淘汰；操作系统使用链表管理页帧，Redis采用大量的链表结果，比如列表底层使用的双向链表，发布订阅，客户端状态等等。
之所以受欢迎，主要还是得益于首先其不需要连续的内存空间，此外其动态插入和删除的效率比较高，相对于数组，其不必每次操作都要同时移动其他数据。虽然其除了存储值本身外，还存储指针，看似比较浪费空间，但更多时候都是瑕不掩瑜，其高校的数据处理要掩盖其内存浪费的劣势。
1、单链表介绍
2、单链表的操作
- 创建；
- 删除；
- 插入；
- 反转；
- 寻找两个单链表的第一个公共结点
- 倒数第k个结点
Python实现：
class Node:
def __init__(self,data=None):
self.data, self.next = data,None
class LinkList:
def __init__(self):
self.tail = self.head = Node()
def isEmpty(self):
if self.head.next is None:
return True
return False
@property
def length(self):
length = 0
cur = self.head
while cur.next is not None:
length += 1
cur = cur.next
return length
def insert(self,value,index=-1):
if index > self.length:
raise ValueError('the index is longer than length')
node = Node(value)
cur_node,cur_pos = self.head,0
if self.length == 0 or index == self.length or index == -1 :
self.tail.next = node
self.tail = self.tail.next
else:
while cur_pos < index:
cur_node = cur_node.next
cur_pos += 1
node.next = cur_node.next
cur_node.next = node
def remove(self,index=-1):
if index > self.length:
raise ValueError('the index is longer than length')
if index == self.length or index == -1:
cur = self.head
while cur.next != self.tail:
cur = cur.next
cur.next = None
self.tail = cur
pre_node,cur_pos = self.head,0
while cur_pos < index - 1:
pre_node = pre_node.next
cur_pos += 1
pre_node.next = pre_node.next.next
def iterprint(self):
cur = self.head
while cur != self.tail:
cur = cur.next
print cur.data
if __name__ == "__main__":
linklist = LinkList()
linklist.insert(3)
linklist.insert(5)
linklist.insert(8)
linklist.insert(4,1)
linklist.iterprint()
linklist.remove(2)
linklist.iterprint()
JAVA实现：
@Data
class Node<E> {
private E value;
private Node<E> next;
}
public class SingleLinkList<E> {
@Getter
private int size;
private Node<E> head;
private Node<E> tail;
SingleLinkList(){
this.size = 0;
head = new Node<E>();
tail = new Node<E>();
head.setValue(null);
head.setNext(null);
tail.setValue(null);
tail.setNext(null);
}
public boolean insert(E x){
Node<E> node = new Node<>();
node.setValue(x);
if (size == 0){
head.setNext(node);
node.setNext(tail);
}else {
Node<E> cur = head;
while (cur.getNext() != tail){
cur = cur.getNext();
}
cur.setNext(node);
node.setNext(tail);
}
size++;
return true;
}
public boolean remove(int index){
if (index > size - 1)
return false;
int curIndex = 0;
Node<E> curNode = head.getNext();
while (curIndex < index -1 && curNode.getNext() != tail){
curIndex ++;
curNode = curNode.getNext();
}
if (curIndex == index - 1){
Node<E> afterCurNode = curNode.getNext();
curNode.setNext(afterCurNode.getNext());
afterCurNode.setNext(null);
afterCurNode.setValue(null);
return true;
}
return false;
}
public String toString(){
if (size == 0){
return "";
}
StringBuilder stringBuilder = new StringBuilder();
Node<E> e = head.getNext();
while (e!=tail){
stringBuilder.append(e.getValue());
e = e.getNext();
}
return stringBuilder.toString();
}
/**
* 链表反转
*/
public void reverse(){
if (size == 0){
return;
}else {
Node<E> pre = head;
Node<E> cur = head.getNext();
while(cur != null){
Node<E> next = cur.getNext();
cur.setNext(pre);
pre = cur;
cur = next;
}
Node<E> tmp = head;
head = tail;
tail = tmp;
}
}
public static void main(String[] args){
SingleLinkList<Integer> singleLinkList = new SingleLinkList<Integer>();
singleLinkList.insert(3);
singleLinkList.insert(2);
singleLinkList.insert(4);
singleLinkList.insert(1);
singleLinkList.insert(15);
System.out.println(singleLinkList);
System.out.println(singleLinkList.remove(4));
System.out.println(singleLinkList);
singleLinkList.reverse();
System.out.println(singleLinkList);
}
}代码实现（C语言）：
#include<stdio.h>
#include<stdlib.h>
#include<time.h>
//定义结构体
typedef struct node {
int data;
struct node *next;
}Node;
void print_chain(Node *L)
{
if(L==NULL||L->next==NULL)
return;
Node *cur = L->next;
while(cur!=NULL)
{
printf("%d,",cur->data);
cur = cur->next;
}
printf("\n");
}
/*
创建的链表第一个元素不存储数据，只有指向第一个节点的指针。
其中head是头指针，r是尾指针。
随机数使用rand函数生成。
*/
Node *create_linkedlist(int n)
{
int i;
srand(time(0));
Node *head;
head = (Node*)malloc(sizeof(Node));
if(head==NULL)
return;
head->next = NULL;
Node *r = head;
Node *p;
for(i=0;i<n;i++)
{
p = (Node*)malloc(sizeof(Node));
if(p==NULL)
return;
p->data = i+1;
r->next = p;
r = p;
}
r->next = NULL;
return head;
}
int get_length(Node *L)
{
int length = 0;
if(L==NULL)
return 0;
Node *cur = L;
while(cur!=NULL)
{
length += 1;
cur = cur->next;
}
return length;
}
//删除结点
Node *delete_node(Node *L,int index)
{
//如果结点位置超过链表长度，就直接退出。
int length = get_length(L);
if(index<1 || index >length)
return;
Node *cur = L;
int i = 1;
while(cur->next!=NULL && i<index)
{
cur = cur->next;
++i;
}
//将删除结点的前一个结点的next指针直接指向所删除结点的下一个元素。
Node *p = cur->next;
cur->next = p->next;
printf("delete item:%d\n",p->data);
free(p);
return L;
}
//插入结点
Node *insert_node(Node *L,int index,int data)
{
int i = 1;
Node *insertNode = (Node*)malloc(sizeof(Node));
if(insertNode==NULL)
return;
Node *p = L;
while(p->next!=NULL && i<index)
{
p = p->next;
++i;
}
if(!p || i>index)
return;
/*要插入的位置index的结点是p，其下一个结点是q，现将p的next指针指向要插入的结点，然后将插入结点的next指针指向q。
insertNode->data = data;
insertNode->next = p->next;
p->next = insertNode;
return L;
}
Node *Reverse(Node *L)
{
Node *Pre = NULL;
Node *cur = L->next;
while(cur!=NULL)
{
Node *q = cur->next;
cur->next = Pre;
Pre = cur;
cur = q;
}
Node *ReverseHead = (Node*)malloc(sizeof(Node));
ReverseHead->next = Pre;
return ReverseHead;
}
//寻找两个单链表的第一个公共结点
Node *find_first_common_node(Node* L1,Node* L2)
{
int L1Length = get_length(L1);
int L2Length = get_length(L2);
int length_diff = L1Length - L2Length;
/*首先计算两个链表的长度插，让长的指针先走，走了他们长度差的步数之后，让两指针同时移动，目的是为了保证他俩可以同时到达第一个公共结点。*/
Node *LinkLong = L1;
Node *LinkShort = L2;
if(length_diff<0)
{
length_diff=L2Length-L1Length;
LinkLong = L2;
LinkShort = L1;
}
for(int i=0;i<length_diff;i++)
LinkLong = LinkLong->next;
while(LinkLong!=NULL && LinkShort!=NULL && LinkLong->data!=LinkShort->data)
{
LinkLong = LinkLong->next;
LinkShort = LinkShort->next;
}
return LinkLong;
}
//寻找倒数第k个结点
/*倒数第K个结点，也就是正数n-k+1，但是总长度n需要遍历整个链表得到，因此这里使用两个指针，使两个指针步长相差k-1,当前一个指针走到了链表尾部，那么后一个指针就是所找的位置*/
Node* find_reverse_k_node(Node* L,int k)
{
Node *p = L;
Node *q = L;
for(int i=1;i<k;i++)
q = q->next;
while(q->next!=NULL)
{
p = p->next;
q = q->next;
}
return p;
}
int main(void)
{
int n = 10;
Node *chain = create_linkedlist(n);
print_chain(chain);
printf("\n");
Node *del = delete_node(chain,3);
print_chain(del);
printf("\n");
Node *ins = insert_node(chain,3,100);
print_chain(ins);
return 0;
}
输出：
1,2,3,4,5,6,7,8,9,10,
delete item:3
1,2,4,5,6,7,8,9,10,
1,2,100,4,5,6,7,8,9,10,
10,9,8,7,6,5,4,100,2,1,
时间复杂度分析：如果是要寻找第i个结点的元素，那链表和数组的时间复杂度是一样，但要向第i个位置添加n个结点，链表明显占优。数组插入一个元素，要移动其他1-n个元素，时间复杂度为O(1)，链表只需要改变前后元素的指针，时间复杂度为O(1)。
--------EOF---------
微信分享/微信扫码阅读
微信分享/微信扫码阅读
